Description

Cow Land 总共有 $N$ 个不同的景点（ $2 \leq N \leq 10^5$ ）。 一共有 $n-1$ 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。

每个景点 $i$ 都有一个享受值 $e_i$ ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。

从景点 $i$ 到景点 $j$ 的奶牛们可以欣赏从景点 $i$ 到景点 $j$ 的路上的所有景观。这条路线的享受值为景点 $i$ 到景点 $j$ 的路上的所有景点（包括景点 $i$ 和景点 $j$ ）的享受值按位进行异或运算的结果。

请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

Input Format

输入的第一行包含两个整数， $N,Q$（$1 \leq Q \leq 10^5$）。

接下来一行包含 $N$ 个整数，其中第 $i$ 个整数 $e_i$ 代表景点 $i$ 的享受值。

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

最后 $Q$ 行，每行包含 3 个整数，表示一个操作，具体内容如下：

1. 1 i v，表示将 $e_i$ 修改为 $v$ 。
2. 2 i j，表示询问从景点 $i$ 到景点 $j$ 的路线的享受值为多少。

Output Format

对于每个 2 操作，输出对应查询的结果。

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

Hint

子任务：对于 $50\%$ 的数据，没有修改操作。