AT_2_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$。