22453번 - A + B 다국어

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

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

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

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

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ビット目とは最下位ビットを表す。

入力は以下の形式で与えられる。

$N$ $A$ $B$

$Q_{1}$

...

$Q_{N}$

1行目にクエリの数N,2進数A, Bが与えられる。

2～N+1行目には以下の様なクエリが与えられる。

• Q

• A $i$

• B $i$

Qが出力クエリを、A $i$,B $i$はそれぞれ$A$の最下位ビットから$i$ビット目、$B$の最下位ビットから$i$ビット目を反転させる変更クエリを表している。

出力クエリごとに答えを1行に出力せよ。

入力中の各変数は以下の制約を満たす。

• $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になることはない