题目描述

给一棵含有 $n$ 个结点的有根树，根结点为 $1$，编号为 $i$ 的点有点权 $a_i$ $(i \in [1, n])$。现在有两种操作，格式如下：

• $1\ x\ y$ 该操作表示将点 $x$ 的点权改为 $y$。
• $2\ x$ 该操作表示查询以结点 $x$ 为根的子树内的所有点的点权的异或和。

现有长度为 $m$ 的操作序列，请对于每个第二类操作给出正确的结果。

输入格式

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻整数之间使用一个空格分隔。

接下来 $n-1$ 行，每行包含两个正整数 $u_i, v_i$，表示结点 $u_i$ 和 $v_i$ 之间有一条边。

接下来 $m$ 行，每行包含一个操作。

输出格式

输出若干行，每行对应一个查询操作的答案。

4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2

4
5
6

提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$n, m \leq 1000$；
• 对于所有评测用例，$1 \leq n, m \leq 100000$，$0 \leq a_i, y \leq 100000$，$1 \leq u_i, v_i, x \leq n$。