异或查询

题目描述

有长度为 $N$ 的整数数列 $A$。

你从现在开始要处理关于这个数列的 $Q$ 个查询。在第 $i$ 个查询中，给定 $T_i, X_i, Y_i$，请进行以下处理：

• 当 $T_i = 1$ 时

  将 $A_{X_i}$ 替换为 $A_{X_i} \oplus Y_i$

• 当 $T_i = 2$ 时

  输出 $A_{X_i} \oplus A_{X_i + 1} \oplus A_{X_i + 2} \oplus \dots \oplus A_{Y_i}$

其中，$a \oplus b$ 表示 $a$ 与 $b$ 的按位异或。

输入格式

输入按以下格式从标准输入给出：

$N$ $Q$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$
$T_1$ $X_1$ $Y_1$
$T_2$ $X_2$ $Y_2$
$T_3$ $X_3$ $Y_3$
$\hspace{22pt} \vdots$
$T_Q$ $X_Q$ $Y_Q$

输出格式

对于每个满足 $T_i = 2$ 的查询，按顺序每行输出 $1$ 个答案。

样例

3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3

0
1
2

第 $1$ 个查询输出 $1 \oplus 2 \oplus 3 = 0$。

第 $2$ 个查询输出 $2 \oplus 3 = 1$。

第 $3$ 个查询将 $A_2$ 替换为 $2 \oplus 3 = 1$。

第 $4$ 个查询输出 $1 \oplus 3 = 2$。

10 10
0 5 3 4 7 0 0 0 1 0
1 10 7
2 8 9
2 3 6
2 1 6
2 1 10
1 9 4
1 6 1
1 6 3
1 1 7
2 3 5

1
0
5
3
0

数据范围

• $1 \le N \le 300000$
• $1 \le Q \le 300000$
• $0 \le A_i \lt 2^{30}$
• $T_i$ 是 $1$ 或 $2$
• 若 $T_i = 1$，则 $1 \le X_i \le N$ 且 $0 \le Y_i \lt 2^{30}$
• 若 $T_i = 2$，则 $1 \le X_i \le Y_i \le N$
• 输入均为整数

提示

什么是按位异或

整数 $A, B$ 的按位异或 $A \oplus B$ 定义如下：

• 将 $A \oplus B$ 用二进制表示时，$2^k$（$k \geq 0$）位的数字是：当 $A, B$ 用二进制表示时 $2^k$ 位的数字中只有一方为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（用二进制表示：$011 \oplus 101 = 110$）。