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

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

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

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

2進数A,Bが与えられた時、以下の様なクエリを処理せよ。

• 出力クエリ: max{x を2進数で表したときの、1の数 | A ≤ 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 ≤ N < 300,000
• 1 ≤ |A|,|B| ≤ 300,000 (|A|はAの長さ)
• A i というクエリでは 0 ≤ i < |A|
• B i というクエリでは 0 ≤ 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

---