在一个遥远的国度里，有 $n$ 座城镇，编号为 $1$ 到 $n$ ，其中最为繁华的 $1$ 号城镇是整个国家的首都。城镇间有 $n-1$ 条双向的道路，长度都一样，且任意两座城镇间都可以通过这些道路相互到达，由此形成了一棵有根树的结构。

国度中的人们分属若干个家族。由于历史原因，人们以一种奇特的方式聚居在一起：对于每个家族，所有家族成员的居住地到首都的距离都一样；并且对于任意一个到首都距离相同的城镇集合，这些城镇里都只住着某一个家族的人。这样一来，国度中的家族数量就与这棵树的深度相同，每个家族都拥有处于某一个深度的所有城镇。

这是一个盛产宝石的国度，出口宝石是国家的支柱产业，但宝石的开采很需要运气，所以人们发明了一套占卜仪式，用每座城镇中目前的宝石库存量来判断接下来的一段时间里宝石的产量如何。仪式会由某一座城镇发起，设它的编号为 $x$ ，所有在 $x$ 的子树中且距离 $x$ 不超过 $L$ 的城镇都会派出一名代表，携带城镇里的所有宝石库存来到城镇$x$；在这里，每个家族的宝石库存会被堆在一起，形成不超过 $L+1$ 个宝石堆。然后，代表幸运与厄运的两位祭司会轮流行动，每次从某个非空的宝石堆里取走至少一枚宝石，直到最后一枚宝石被取走为止，取走这最后一枚宝石的祭司就获胜了，他所代表的力量将决定接下来一段时间内的收成。祭司们都是绝顶聪明的人，仪式要求他们按照对自己最优的策略行动，而他们也确实是这样做的。仪式结束后，所有宝石会被归还到原来的城镇中。

稍有常识的人都会看出，这实际上就是一场Nim游戏，最终的结果由所有宝石堆中宝石个数的异或和决定。聪明的你自然也不例外，现在你获得了总共 $m$ 条消息，每条表示某座城镇中进行了一场占卜，或是某座城镇的宝石库存发生了变化；你希望对于每次占卜，算出这个异或和。

输入格式

第一行两个正整数 $n$ 和 $m$ ，表示城镇数量与要处理的消息数量。

第二行 $n$ 个非负整数 $c_1, c_2, \ldots, c_n$ ，其中 $c_i$ 表示编号为 $i$ 的城镇中宝石的初始库存。

接下来 $n-1$ 行，每行两个正整数 $x$ 和 $y$ ，描述一条连接城镇 $x$ 和城镇 $y$ 的双向道路。

最后 $m$ 行，每行描述一条消息，属于下面两种当中的某一种：

• 1 x v，表示城镇 $x$ 的宝石库存变为 $v$ 颗；
• 2 x L，表示城镇 $x$ 举行了一次占卜仪式，子树中所有距离不超过 $L$ 的城镇都参加了。

输出格式

对于每个消息 $2$ ，输出一行一个非负整数，表示对应的异或和。

样例数据

样例输入

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

样例输出

6
4
1
7

子任务

• 子任务1（7分）：$n, m \leq 10^3$。
• 子任务2（13分）：$L \leq 20$。
• 子任务3（15分）：树的叶子数量不超过 $20$ 。
• 子任务4（15分）：宝石库存不会变化，即只有消息 $2$ 。
• 子任务5（20分）：$n, m \leq 30000$。
• 子任务6（30分）：无特殊限制。

对于所有数据，$1 \leq n, m \leq 10^5, 0 \leq L < n, 0 \leq c_i, v \leq 10^9$。