プログラミングコンテストの合宿で出す問題のアイディアが出ずに困っていたイクタ君は、ある日友人に相談した。

イクタ君「こういうアルゴリズムを使わないと解けないような問題が出したいんですけど、なにかありませんかね？」

友人「それではこういうものを考えたらいいんじゃないですか」

このようにしてその友人は以下のような問題の原案となるアイデアを考えてくれた。

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