토너먼트

한 해설자가 싱글 엘리미네이션(단판 토너먼트) 방식의 가구 분해 대회를 24시간 중계하게 되었다. 각 참가자는 가구 분해 실력 값을 가지며, 이 값은 $1$ 이상 1,000,000,000 이하의 정수이다. 모든 맞대결에서 실력 값이 더 큰 참가자가 이기고 다음 라운드로 올라가며, 진 참가자는 탈락한다. 어느 시점에서든 모든 참가자의 실력 값은 서로 다르다고 보장되므로 무승부는 발생하지 않는다.

토너먼트 트리에는 $2^N$개($1 \le N \le 20$)의 자리(위치)가 있으며, 왼쪽부터 $1, 2, \ldots, 2^N$번으로 번호가 매겨져 있다. 첫 라운드에서는 $1$번과 $2$번, $3$번과 $4$번, ... 참가자가 각각 맞붙는다. 이후 각 라운드에서는 직전 라운드의 처음 두 경기 승자끼리, 그 다음 두 경기 승자끼리, ... 대결한다. $N$번의 라운드가 끝나면 한 명의 우승자가 남는다. 예를 들어 $N = 2$일 때 토너먼트 트리는 다음과 같다.

여기서 $A$는 $1$번과 $2$번의 승자, $B$는 $3$번과 $4$번의 승자, $C$는 $A$와 $B$의 승자이며, $C$가 이 토너먼트의 우승자이다.

후원 계약 때문에 시간이 지나면서 일부 참가자가 교체된다. 새로운 사람이 들어올 때마다 토너먼트를 처음부터 다시 진행한다.

$M$개($1 \le M \le 1{,}000{,}000$)의 명령이 주어질 때(입력 형식 참고), 여러 시점에서의 토너먼트 통계를 계산하는 프로그램을 작성하라.

첫째 줄에 두 정수 $N$($1 \le N \le 20$)과 $M$($1 \le M \le 1{,}000{,}000$)이 공백 하나로 구분되어 주어진다.

다음 $2^N$개의 줄에는 각각 정수 $S_i$가 주어지며($i$는 $1$부터 $2^N$까지), 이는 토너먼트 트리의 위치 $i$에 있는 초기 참가자의 실력 값이다.

그 다음 $M$개의 줄에는 각각 다음 세 가지 형식 중 하나의 명령이 주어진다.

• R i S — 위치 $i$의 참가자를 제거하고 실력 값이 $S$인 새 참가자로 교체한다. 그런 다음 토너먼트를 다시 진행한다.
• W — 현재 토너먼트의 우승자를 구하여 그 참가자의 위치 $i$($1$ 이상 $2^N$ 이하)를 출력한다.
• S i — 현재 토너먼트에서 위치 $i$의 참가자가 이긴 라운드 수를 출력한다.

각 W 또는 S i 명령마다 해당하는 정수를 한 줄에 하나씩 출력한다.