牛乐园是一个特殊的牛游乐园，牛们可以在里面漫步，吃草，参观景点（其中过山车特别受牛欢迎）。

其中共有 $N$ 个不同的景点。

某些景点之间通过道路（总共 $N-1$ 条）直接相连，任何两个景点之间都存在一条由若干道路组成的唯一路径。

每个景点 $i$ 都有一个快乐值 $e_i$，它可以在一天内发生改变，因为有的景点在早上更具吸引力，而有的景点在下午更具吸引力。

一头奶牛从景点 $i$ 到景点 $j$，可以参观从 $i$ 到 $j$ 的路径上的所有景点。

奇怪的是，这条路径的总快乐值是路径中经过的所有景点（包括 $i$ 和 $j$）的快乐值按位异或（XOR）的结果。

请帮助奶牛们确定他们下次牛乐园之旅的计划路线的总快乐值是多少。

输入格式

第一行包含两个整数 $N$ 和 $Q$，表示景点数量和询问数量。

第二行包含 $N$ 个整数，$e_1,e_2,…,e_N$。

接下来 $N-1$ 行，每行包含两个整数 $a,b$，表示景点 $a$ 和景点 $b$ 之间存在一条道路。

接下来 $Q$ 行，每行包含三个整数，表示对某个 $e_i$ 的更新或对某条路线的总快乐值的询问，如果形式为 1 i v，则表示将 $e_i$ 更新为值 $v$，如果形式为 2 i j，则表示查询连接景点 $i$ 和 $j$ 的路线的总快乐值。

输出格式

对于每个形式为 2 i j 的询问，输出一个整数表示查询线路的总快乐值。

每个查询结果占一行。

数据范围

$2 \le N \le 10^5$,
$1 \le Q \le 10^5$,
$0 \le e_i,v \le 10^9$,
$1 \le a,b \le N$

输入样例：

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

输出样例：

21
20
4
20