问题描述

给一棵含有 $n$ 个结点的有根树，根结点为 $1$，编号为 $i$ 的点有点权 $a_i(i∈[1,n])$。现在有两种操作，格式如下：

• $1$ $x$ $y$：该操作表示将点 $x$ 的点权改为 $y$。
• $2$ $x$：该操作表示查询以结点 $x$ 为根的子树内的所有点的点权的异或和。

现有长度为 $m$ 的操作序列，请对于每个第二类操作给出正确的结果。

输入格式

输入的第一行包含两个正整数 $n,m$，用一个空格分隔。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$，相邻整数之间使用一个空格分隔。

接下来 $n-1$ 行，每行包含两个正整数 $u_i,v_i$，表示结点 $u_i$ 和 $v_i$ 之间有一条边。

接下来 $m$ 行，每行包含一个操作。

输出格式

输出若干行，每行对应一个查询操作的答案。

样例

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

样例输出

4
5
6

评测用例规模与约定

对于 $30\%$ 的评测用例，$n,m≤1000$；

对于所有评测用例，$1≤n,m≤100000$，$0≤a_i,y≤100000$，$1≤u_i,v_i,x≤n$。