TOURNEY  Tourney
Don Cherry has been hired to run 24hour coverage of a series of singleelimination, bracketstyle, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between $1$ and $10^9$. In every headtohead match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guaranteed that, at any time, the skill levels of all competitors are distinct, so there are no ties.
There are $2^N$ ($1 \leq N \leq 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 in a furniture disassembly race, as do competitors 3 and 4, etc. In each subsequent round, the winners of the first two matches from the previous round compete, as do the winners of the following two, etc. After $N$ rounds, a single winner remains. For example, when $N=2$, the tourney tree looks like this:
where A represents the winner of the match between competitors 1 and 2, B represents the winner of the match between competitors 3 and 4, and C represents the winner of the match between A and B. The winner of this tourney is C.
Because of sponsorship contracts, some competitors will be replaced over time. After any new person comes in, a new tourney is held.
In order to help Don Cherry, you must write a program to compute certain tourney statistics at various points in time, given a sequence of $M$ ($1 \leq M \leq 10^6$) commands  see the input format below.
Input
The first line of input contains two integers, $N$ and $M$.
The next $2^N$ lines, for $i$ from $1$ to $2^N$, each contain one integer $S_i$, indicating the skill level of the initial competitor at position $i$ in the tourney tree.
Each of the following $M$ lines will be a command in one of three formats:
 "R $i$ $s$" means that the competitor at position $i$ is removed, and replaced with a new one with skill level $s$. A new tourney should then be held.
 "W" means that your program should determine who won the current tourney. Print out the position $i$ (between $1$ and $2^N$) of this competitor.
 "S $i$" means that your program should print out the number of rounds that the competitor at position $i$ won in the current tourney.
Output
For each "W" or "S $i$" command in the input, print out the corresponding integer on a line by itself.
Example
Input:
2 8
30
20
10
40
S 1
W
R 4 9
S 4
W
R 2 35
S 2
W
Output:
1
4
0
1
2
2
Explanation of Sample:
The results of the initial tourney are as follows:
As can be seen, competitor 1 wins 1 match, and competitor 4 wins the entire tourney. After this, competitor 4 is replaced by a new competitor with skill level 9. As can be seen below, this causes a different outcome for the tourney held after the third command:
Finally, the state of the tourney tree after the next competitor replacement (caused by the sixth command) is:
hide comments
Shubham:
20140904 07:20:01
Instead of using scanf for character input, use cin. Costed me 3 WA's 

rahulSan:
20140730 20:30:44
5 th case tle or wrong answer, please help...


vilay:
20130701 16:44:50
getting many WA dont know why please look at my submission id:9585861, and provide some more tricky cases


Narendra yadav:
20130614 14:42:47
Behaviour of scanf() and %c is confusing.


RAJDEEP GUPTA:
20130602 19:07:41
TL is quite relaxed. :) 
Added by:  SourSpinach 
Date:  20130530 
Time limit:  8s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem, used in the 2013 CCC Stage 2 