题目描述

長さ $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$ のビット単位 xor を表します。
ビット単位 xor とは 整数 $A,\ B$ のビット単位 xor 、$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$)。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $ A_1\ \hspace{7pt}\ A_2\ \hspace{7pt}\ A_3\ \hspace{5pt}\ \dots\ \hspace{5pt}\ 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$ 行に $1$ つずつ、順に出力せよ。

题目大意

维护序列 $A_1,A_2,\dots,A_n$。

$Q$ 次操作，每次给出 $T,X,Y$：

• $T=1$：将 $A_X$ 替换为 $A_X \oplus Y$
• $T=2$：输出 $A_{X}\oplus A_{X+1}\oplus A_{X+2}\oplus\dots\oplus A_Y$。

其中 $\oplus$ 是按位异或。

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

0
1
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$
• 入力は全て整数

Sample Explanation 1

$1$ 個目のクエリでは $1\ \oplus\ 2\ \oplus\ 3\ =\ 0$ を出力します。 $2$ 個目のクエリでは $2\ \oplus\ 3\ =\ 1$ を出力します。 $3$ 個目のクエリでは $A_2$ が $2\ \oplus\ 3\ =\ 1$ で置き換えられます。 $4$ 個目のクエリでは $1\ \oplus\ 3\ =\ 2$ を出力します。