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$ 个查询，请按顺序处理这些查询。 每个查询有两种类型之一： - 类型 $1$：格式为 `1 i a b`。将 $A_i$ 的值改为 $a$，将 $B_i$ 的值改为 $b$。 - 类型 $2$：格式为 `2 Y 0 0`。解决以下问题： - 对于非负整数 $S$，定义非负整数序列 $X = (X_0, X_1, \ldots, X_N)$ 如下： - $X_0 = S$ - 对于每个 $1 \le i \le N$，$X_i = \begin{cases} X_{i-1} \oplus A_i & \text{如果 } X_{i-1} \equiv 1 \pmod{2} \\ X_{i-1} \oplus B_i & \text{如果 } X_{i-1} \equiv 0 \pmod{2} \end{cases}$ - 判断是否存在一个适当的非负整数 $S$ 使得 $X_N = Y$。如果存在这样的 $S$，输出最小的 $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$ 查询的答案。

### 约束条件 - 所有输入均为整数 - $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 < 2^{60}$ - 至少存在一个类型 $2$ 的查询 ### 部分分数 - 如果在满足附加约束 $Q = 1$ 的数据集上正确解答，则可获得 $30$ 分。 ### 样例解释 1 - $A = (0), B = (1)$，因此如果 $S$ 是奇数，则 $X_N = S$；如果 $S$ 是偶数，则 $X_N = S \oplus 1$。 - 第一个查询中，$Y = 5$。当 $S$ 为 $4$ 或 $5$ 时，$X_N = 5$，因此输出最小值 $4$。 - 第二个查询中，$Y = 6$。不存在使 $X_N = 6$ 的 $S$，因此输出 `-1`。 - 第三个查询中，$Y = 7$。当 $S$ 为 $6$ 或 $7$ 时，$X_N = 7$，因此输出最小值 $6$。