Cow Land 是专为奶牛建造的游乐园，她们可以四处漫步，吃美味的草，参观不同的奶牛游乐设施（其中奶牛过山车尤其受欢迎）。

共有 $N$ 个不同设施（$2 \leq N \leq 10^5$）。某些设施之间有道路相连，共 $N-1$ 条，且任意两座设施之间都有唯一一条由这些道路组成的路线。设施 $i$ 的整数快乐值为 $e_i$，一天中可能发生变化，因为有些设施早晨更吸引人，有些下午晚些时候更吸引人。

从设施 $i$ 前往设施 $j$ 的奶牛会体验从 $i$ 到 $j$ 路线上的所有设施。奇妙的是，整条路线的总快乐值是沿途全部快乐值的按位异或，包括设施 $i$ 和 $j$ 的值。

请帮助奶牛计算下次游览 Cow Land 时计划走的各条路线的快乐值。

输入格式

输入第一行包含 $N$ 和询问数量 $Q$（$1 \leq Q \leq 10^5$）。下一行包含 $e_1 \ldots e_N$（$0 \leq e_i \leq 10^9$）。接下来 $N-1$ 行各用两个整数设施编号 $a$ 和 $b$（均在 $1 \ldots N$ 范围内）描述一条道路。最后 $Q$ 行各描述对某个 $e_i$ 的修改，或对一条路线快乐值的询问。“1 $i$ $v$”表示将 $e_i$ 改为 $v$；“2 $i$ $j$”表示询问连接设施 $i$ 和 $j$ 的路线的快乐值。

占至多 50% 分数的测试数据中，设施的值不会变化。

输出格式

对每个“2 $i$ $j$”形式的询问，在单独一行输出从 $i$ 到 $j$ 的路线的快乐值。

样例

输入格式 1

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

输出格式 1

21
20
4
20

出题人：Charles Bailey