欧盟的各个国家可以被看作一个图，其中任意两个国家之间恰好存在一条路径，即一棵树。国家编号为 $1$ 到 $n$，其中克罗地亚的编号为 $1$。由于今年马尔纳先生担任欧盟轮值主席，需要组织多次会议。各国代表很奇怪，他们非常喜欢成群结队地移动。因此，在前往克罗地亚的旅途中，首先，所有在旅途中经过某个国家的代表会在该国集合，然后与该国代表一起作为一组继续前往下一个国家，直到所有人最终在节点 $1$ 集合开会。（详细解释请参考第一个样例的说明。）

不幸的是，欧盟国家之间引入了人员关税！每个国家都有已知的关税 $c_i$，每个人在进入该国时都必须支付此费用，当然，该国代表在自己的国家内无需支付关税。然而，海关人员对欧盟的理念持讽刺态度，因此他们在每个国家决定对进入该国的最大群体收取双倍关税；如果存在多个同样大小的最大群体，则对来自编号最小的国家的那一组收取双倍关税。欧盟内部变动频繁，马尔纳先生请求你支持以下三种关键操作：

1 $v$ - 如果现在举行会议，国家 $v$ 的代表需要支付多少钱？ 2 $v$ $c$ - 国家 $v$ 将关税更改为 $c$。 3 $v$ $c$ - 出现了一个编号为 $k$ 的新国家（$k$ 是不存在该编号的最小自然数），其关税为 $c$，并与国家 $v$ 相连。

马尔纳先生在所有事务中感到迷茫，请求你编写一个程序，以便能够快速回答这些问题。接下来的两周至关重要！

输入格式

第一行包含数字 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示初始国家数量和操作数量。 下一行包含 $n$ 个数字，其中第 $i$ 个数字表示 $c_i$ ($0 \le c_i \le 10^9$)，即第 $i$ 个国家的关税。 接下来的 $n - 1$ 行包含数字 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示国家 $u_i$ 和 $v_i$ 之间由一条边相连。

令 $lastans$ 表示在某一时刻最后一次类型 1 操作的答案，如果之前没有类型 1 操作，则 $lastans = 0$。令 $k$ 为该时刻为止存在的最大国家编号。令 $\oplus$ 表示按位异或运算。

如果第 $i$ 个事件是类型 1，则该行包含数字 $1$ $v'$ ($0 \le v' \le 10^{18}, 1 \le v \le k$)，其中 $v = v' \oplus lastans$。 如果第 $i$ 个事件是类型 2，则该行包含数字 $2$ $v'$ $c'$ ($0 \le v', c' \le 10^{18}, 1 \le v \le k, 0 \le c \le 10^9$)，其中 $v = v' \oplus lastans, c = c' \oplus lastans$。 如果第 $i$ 个事件是类型 3，则该行包含数字 $3$ $v'$ $c'$ ($0 \le v', c' \le 10^{18}, 1 \le v \le k, 0 \le c \le 10^9$)，其中 $v = v' \oplus lastans, c = c' \oplus lastans$。

输出格式

在第 $i$ 行输出对第 $i$ 个类型 1 操作的回答。

样例

输入 1

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

输出 1

20
4

说明 1

因为直到第四个操作才是第一个类型 1 操作，$lastans = 0$，操作未改变。国家 2 的代表前往国家 3，支付双倍关税 6，因为它是进入该城市的唯一群体，因此也是最大群体。现在来自城市 2 和 3 的代表一起进入城市 6，因为该群体由两人组成，而来自节点 7 的群体只有一人，他们支付双倍关税，即城市 2 的代表支付关税 6。此后，国家 2、3、6 和 7 的代表一起前往国家 1，再次作为最大群体支付双倍关税，因此国家 2 的代表支付 8。总金额为 $6 + 6 + 8 = 20$。

在第五个操作中，$lastans = 20$，因此 $v = 16 \oplus 20 = 5$。国家 5 的代表独自前往国家 1，因为不是最大群体，所以支付单倍关税，即 4。

输入 2

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

输出 2

6
14
26