実行時間制限: 8 sec / メモリ制限: 128 MB
プログラミングコンテストの合宿で出す問題のアイディアが出ずに困っていたイクタ君は、ある日友人に相談した。
イクタ君「こういうアルゴリズムを使わないと解けないような問題が出したいんですけど、なにかありませんかね?」
友人「それではこういうものを考えたらいいんじゃないですか」
このようにしてその友人は以下のような問題の原案となるアイデアを考えてくれた。
2進数A,Bが与えられた時、以下の様なクエリを処理せよ。
出力クエリ: max{x を2進数で表したときの、1の数 | A \leq x < A+B }を出力
A変更クエリ: Aの最下位ビットからiビット目(0-origin)を反転
B変更クエリ: Bの最下位ビットからiビット目(0-origin)を反転
iビット目というのが 0-origin で表されていることに注意せよ。 つまり、Aの最下位ビットから0ビット目とは最下位ビットを表す。
Input
入力は以下の形式で与えられる。
N A B
Q1
...
QN
1行目にクエリの数N,2進数A, Bが与えられる。
2~N+1行目には以下の様なクエリが与えられる。
Q
A i
B i
Qが出力クエリを、A i,B iはそれぞれAの最下位ビットからiビット目、Bの最下位ビットからiビット目を反転させる変更クエリを表している。
Constraints
入力中の各変数は以下の制約を満たす。
1 \leq N < 300,000
1 \leq |A|,|B| \leq 300,000 (|A|はAの長さ)
A i というクエリでは 0 \leq i < |A|
B i というクエリでは 0 \leq i < |B|
Bが0になることはない
Output
出力クエリごとに答えを1行に出力せよ。
Sample Input 1
4 10000 00101 Q A 0 B 1 Q
Output for the Sample Input 1
3 4
最初の出力クエリでは A=10000, B=00101, A+B=10101なので求めるxは10011
次の出力クエリでは A=10001, B=00111, A+B=11000なので求めるxは10111
Sample Input 2
9 0110111101 0010100111 Q B 4 Q A 4 Q B 9 Q A 8 Q
Output for the Sample Input 2
9 9 9 10 9