[USACO19FEB] Cow Land G

题目背景

Cow Land 是一个特殊的奶牛游乐园,奶牛们可以在那里漫步,吃美味的草,并参观不同的景点(尤其过山车特别受欢迎)。

题目描述

Cow Land 总共有 $ N $ 个不同的景点( $ 2 \leq N \leq 10^5 $ )。 一共有 $ n-1 $ 条道路连接任意两个景点,这意味着任意两个景点间只有一条简单路径。 每个景点 $ i $ 都有一个享受值 $ e_i $ ,这个值可能会改变。因为一些景点在早上更有吸引力,而其他景点在下午则更能吸引游客。 从景点 $ i $ 到景点 $ j $ 的奶牛们可以欣赏从景点 $ i $ 到景点 $ j $ 的路上的所有景观。这条路线的享受值为景点 $ i $ 到景点 $ j $ 的路上的所有景点(包括景点 $ i $ 和景点 $ j $ )的享受值按位进行异或运算的结果。 请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

输入输出格式

输入格式


输入的第一行包含两个整数, $ 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 $ 的路线的享受值为多少。

输出格式


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

输入输出样例

输入样例 #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

说明

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