問題文

$1\sim N$ の番号が付いた $N$ 頂点の木が与えられます。

この木の根は頂点 $1$ です。

各頂点にはコストがあり、頂点 $i$ のコストは $C_i$ です。 $(1≤i≤N)$

また、$i$ 番目の辺 $(1 \leq i \leq N-1)$ は 頂点 $a_i$ と頂点 $b_i$ を結びます。

以下のクエリが $Q$ 回与えられるので、処理してください。

• $j$ 回目のクエリ $(1≤j≤Q)$ では以下の操作を行う。

• $T_j=1$ のとき

$C_{x_j}$ を $C_{x_j} \oplus y_j$ で置き換える。

• $T_j=2$ のとき

頂点 $x_j$ を根とする部分木の全ての頂点のコストの xor を出力する。

ただし、 $a\oplus b$ はビット単位の xor を表します。

制約

• $2 \leq N \leq 10^5$

• $1 \leq Q \leq 10^5$

• $0 \leq C_i<2^{10}$ $(1 \leq i \leq N)$

• $1 \leq a_i,b_i \leq N$ $(1 \leq i \leq N-1)$

• $T_j$ は $1$ または $2$ である。 $(1 \leq j \leq Q)$

• $1 \leq x_j \leq N$ $(1 \leq j \leq Q)$

• $T_j=1$ のとき、 $0 \leq y_j < 2^{10}$ $(1 \leq j \leq Q)$

• $T_j=2$ のとき、 $y_j=0$ $(1≤j≤Q)$

• クエリに $T_j=2$ $(1 \leq j \leq Q)$ は少なくとも $1$ つは含まれる。

• 入力は全て整数である。

• 与えられるグラフは木である。

入力

$N$ $Q$

$C_1$ $C_2$ $\dots$ $C_N$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_{N-1}$ $b_{N-1}$

$T_1$ $x_1$ $y_1$

$T_2$ $x_2$ $y_2$

$\vdots$

$T_Q$ $x_Q$ $y_Q$

• $1$ 行目には、 $N$ と $Q$ が空白区切りで与えられる。

• $2$ 行目には、各頂点のコスト $C_1, C_2, \dots, C_N$ が空白区切りで与えられる。

• $3$ 行目から $N+1$ 行目には、 $a_i$ と $b_i$ が空白区切りで与えられる。 $(1 \leq i \leq N-1)$

• $N+2$ 行目から $N+Q+1$ 行目には、 $T_j,~x_j,~y_j$ が空白区切りで与えられる。 $(1 \leq j \leq Q)$

出力

$T_j=2~(1 \leq j \leq Q)$ であるような各クエリについて $1$ 行ずつ出力してください。

最後に改行してください。

サンプル