Tourney

A commentator has been hired to provide 24-hour coverage of a series of single-elimination, bracket-style furniture-disassembly tourneys (tournaments). Each competitor has a furniture-disassembly skill level, an integer between $1$ and 1,000,000,000. In every head-to-head match, the competitor with the larger skill level wins and advances, while the other is eliminated. At any moment the skill levels of all competitors are guaranteed to be distinct, so ties never occur.

There are $2^N$ ($1 \le N \le 20$) competitor positions in the tourney tree, numbered $1, 2, \ldots, 2^N$ from left to right. In the first round, competitors $1$ and $2$ face off, as do competitors $3$ and $4$, and so on. In each later round, the winners of the first two matches of the previous round compete, then the winners of the next two, and so on. After $N$ rounds a single winner remains. For example, when $N = 2$ the tourney tree looks like this:

Here $A$ is the winner of the match between competitors $1$ and $2$, $B$ is the winner of the match between competitors $3$ and $4$, and $C$ is the winner of the match between $A$ and $B$. $C$ is the winner of this tourney.

Because of sponsorship contracts, some competitors are replaced over time. Whenever a new person comes in, a fresh tourney is held.

Given a sequence of $M$ ($1 \le M \le 1{,}000{,}000$) commands (see the input format below), write a program that reports certain tourney statistics at various points in time.

The first line contains two integers $N$ ($1 \le N \le 20$) and $M$ ($1 \le M \le 1{,}000{,}000$), separated by a single space.

The next $2^N$ lines each contain one integer $S_i$ (for $i$ from $1$ to $2^N$): the skill level of the initial competitor at position $i$ in the tourney tree.

Each of the following $M$ lines is a command in one of three formats:

• R i S — the competitor at position $i$ is removed and replaced by a new competitor with skill level $S$. A new tourney is then held.
• W — determine who won the current tourney and print the position $i$ (between $1$ and $2^N$) of that competitor.
• S i — print the number of rounds that the competitor at position $i$ won in the current tourney.

For each W or S i command, print the corresponding integer on its own line.