AT_ttpc2024_2_d Odd Xor

You are given two sequences of non-negative integers $ A $ and $ B $ , each of length $ N $ . Initially, $ A=(A_1, A_2, \ldots, A_N) $ and $ B=(B_1, B_2, \ldots, B_N) $ . You will be given $ Q $ queries. Process them in the order they are given. Each query is one of the following two types: - Type $ 1 $ : Given in the format `1 i a b`. Update the value of $ A_i $ to $ a $ and the value of $ B_i $ to $ b $ . - Type $ 2 $ : Given in the format `2 Y 0 0`. Solve the following problem:> For a non-negative integer $ S $ , define a sequence of non-negative integers $ X = (X_0, X_1, \dots, X_N) $ using the following recurrence: > > > - $ X_0 = S $ > - For each $ 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} $ > > Determine whether it is possible to set a non-negative integer $ S $ such that $ X_N = Y $ . If possible, output the smallest such $ S $ . > If no such $ S $ exists, output `-1`.

The input is given in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $ $ \mathrm{query}_1 $ $ \vdots $ $ \mathrm{query}_Q $ Here, $ \mathrm{query}_i $ represents the $ i $ -th query and is given in one of the following formats: > 1 $ i $ $ a $ $ b $ > 2 $ Y $ 0 0

Let $ q $ be the number of Type $ 2 $ queries. Output $ q $ lines, where the $ i $ -th line contains the answer to the $ i $ -th Type $ 2 $ query.

### Partial Score $ 30 $ points will be awarded for passing the test set satisfying the additional constraint $ Q=1 $ . ### Sample Explanation 1 Given $ A = (0),\ B = (1) $ , the value of $ X_N $ is: - $ X_N = S $ if $ S $ is odd. - $ X_N = S \oplus 1 $ if $ S $ is even. For the first query with $ Y = 5 $ , both $ S = 4 $ and $ S = 5 $ result in $ X_N = 5 $ , so the smallest $ S $ is $ 4 $ . For the second query with $ Y = 6 $ , there is no $ S $ such that $ X_N = 6 $ , so output `-1`. For the third query with $ Y = 7 $ , both $ S = 6 $ and $ S = 7 $ result in $ X_N = 7 $ , so the smallest $ S $ is $ 6 $ . ### Constraints - All inputs are integers. - $ 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) $ - For a Type $ 1 $ query, $ 1 \le i \le N $ , $ 0 \le a, b < 2^{60} $ - For a Type $ 2 $ query, $ 0 \le Y < 2^{60} $ - There is at least one Type $ 2 $ query.