돈 체리는 가구 분해하기 싱글 엘리미네이션 토너먼트를 24시간 진행해야 하는 일을 맏게 됐습니다. 각 선수는 1과 1 000 000 000 사이의 정수로 표현된 가구 분해 스킬 레벨을 가지고 있습니다. 각 1:1 경기에서 스킬 레벨이 더 큰 선수가 승리해 다음 라운드로 진출하고, 패자는 집으로 돌아가야하는 구조입니다. 다행히도 같은 스킬 레벨을 가진 선수가 경기를 치루는 경우는 없습니다.

대회에는 2^N (1 ≤ N ≤ 20)명의 선수 1번부터 2^N번까지 트리 모양의 토너먼트에서 왼쪽부터 순서대로 번호가 붙여져있습니다. 첫 라운드에선 1번과 2번 선수, 3번과 4번 선수 등이 가구 분해 경주를 합니다. 다음 라운드에선 각 경기의 승자끼리 다시 경기를 치뤄, 최종적으로 한 명만 남을 때 까지 시합이 계속 됩니다. 예를들어 N = 2인 경우 토너먼트 트리는 다음과 같습니다.

A는 1번과 2번의 경기에서 승자이고, B는 3번과 4번의 경기에서 승자입니다. C는 A과 B의 경기에서의 승자이자 이 토너먼트의 우승자입니다.

그런데 이 토너먼트와 관련된 계약 때문에 중간중간 선수가 교체되기도 합니다. 선수가 한 번 교체되면 토너먼트는 처음부터 다시 시작하게 됩니다.

돈 체리를 돕기 위해 우리는 여러가지 작업을 하는 프로그램을 만들어야합니다. 전부 M개의 명령이 주어지는데 각 명령에 대한 내용은 입력 형식을 참고하세요.

입력

• 첫 번째 줄에 N (1 ≤ N ≤ 20)과 M(1 ≤ M ≤ 1000000)이 입력됩니다.
• 다음 2^N 줄에 i번째 선수의 스킬 레벨이 입력됩니다.
• 다음 M 줄에 다음 세 명령 중 하나가 주어진 형식으로 입력됩니다.
  • R i S : i번 선수가 스킬 레벨이 S인 선수로 교체되어 토너먼트가 처음부터 다시 시작합니다.
  • W : 현재 토너먼트의 우승자를 출력합니다.
  • S i : i번 선수가 몇 번 이기는지 출력합니다.

출력

입출력 예

입력

2 8
30
20
10
40
S 1
W
R 4 9
S 4
W
R 2 35
S 2
W

출력

1
4
0
1
2
2

출처:CEMC (CCC 2013 Stage 2)
번역:ladown21