問題文

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

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

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

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

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

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

• $T_j=1$ のとき

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

• $T_j=2$ のとき

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

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

制約

• $2\le N\le {10}^5$

• $1\le Q\le {10}^5$

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

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

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

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

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

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

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

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

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

入力

$N$ $Q$
$C_1$ $C_2$ $\dots$ $C_N$
$a_1$ $b_1$
$a_2$ $b_2$
$⋮$
$a_{N-1}$ $b_{N-1}$
$T_1$ $x_1$ $y_1$
$T_2$ $x_2$ $y_2$
$⋮$
$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\le i\le N-1)$

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

出力

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

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

サンプル

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

7

6 3
1 2 3 4 5 6
1 2
1 3
2 4
2 6
4 5
1 6 6
1 4 4
2 2 0

7

2 1
1 2
1 2
2 2 0

2