配点 : $600$ 点

問題文

長さ $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 を表します。

制約

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

入力

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

$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$ つずつ、順に出力せよ。

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