AT_ttpc2024_2_d Odd Xor

長さ $ N $ の非負整数列 $ A,B $ があります。はじめ、 $ A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) $ です。 $ Q $ 個のクエリが与えられるので、与えられた順に処理してください。 各クエリは次の $ 2 $ 種類のどちらかです。 - タイプ $ 1 $ : `1 i a b` の形式で与えられる。 $ A_i $ の値を $ a $ に、 $ B_i $ の値を $ b $ に変更する。 - タイプ $ 2 $ : `2 Y 0 0` の形式で与えられる。次の問題を解く。> 非負整数 $ S $ に対し、非負整数列 $ X = (X_0, X_1, \dots, X_N) $ を次の漸化式で定義します。 > > > - $ X_0 = S $ > - 各 $ 1 \le i \le N $ について、 $ X_i = \begin{cases} X_{i - 1} \oplus A_i & \text{if } X_{i - 1} \equiv 1 \pmod{2} \\ X_{i - 1} \oplus B_i & \text{if } X_{i - 1} \equiv 0 \pmod{2} \end{cases} $ > > 適切に非負整数 $ S $ を設定したとき $ X_N=Y $ とすることができるか判定し、可能な場合は、 $ X_N=Y $ となるような $ S $ の最小値を出力してください。 > $ X_N=Y $ となるような $ S $ が存在しない場合は、`-1` を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $ ただし、 $ \mathrm{query}_i $ は $ i $ 番目のクエリであり、以下のいずれかの形式で与えられる。 > 1 $ i $ $ a $ $ b $ > 2 $ Y $ 0 0

タイプ $ 2 $ のクエリの個数を $ q $ として、 $ q $ 行出力せよ。 $ i $ 行目には $ i $ 個目のタイプ $ 2 $ のクエリに対する答えを出力せよ。

### 部分点 追加の制約 $ Q=1 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 $ A = (0),\ B = (1) $ であるので、 $ S $ が奇数なら $ X_N = S $ 、 $ S $ が偶数なら $ X_N = S \oplus 1 $ となります。 $ 1 $ 個目のクエリでは、 $ Y = 5 $ です。 $ S $ が $ 4 $ または $ 5 $ であれば $ X_N = 5 $ となるので、最小値の $ 4 $ を出力します。 $ 2 $ 個目のクエリでは、 $ Y = 6 $ です。 $ X_N = 6 $ となるような $ S $ は存在しないので、`-1` を出力します。 $ 3 $ 個目のクエリでは、 $ Y = 7 $ です。 $ S $ が $ 6 $ または $ 7 $ であれば $ X_N = 7 $ となるので、最小値の $ 6 $ を出力します。 ### Constraints - 入力はすべて整数 - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 0 \le A_i,B_i < 2^{60} \ (1 \le i \le N) $ - タイプ $ 1 $ のクエリにおいて、 $ 1 \le i \le N $ , $ 0 \le a ,b < 2^{60} $ - タイプ $ 2 $ のクエリにおいて、 $ 0 \le Y \lt 2^{60} $ - タイプ $ 2 $ のクエリが $ 1 $ つ以上存在する