现在有一棵以 $1$ 为根节点的由 $n$ 个节点组成的树，树上每个节点上都有一个权值 $v_i$。

现在有 $Q$ 次操作，操作如下:

• 1 x y，查询节点 $x$ 的子树中的节点权值与 $y$ 异或结果的最大值。
• 2 x y z，查询路径 $x$ 到 $y$ 上点的权值与 $z$ 异或结果的最大值

输入格式

第一行是两个数字 $n, Q$。

第二行是 $n$ 个数字用空格隔开，第 $i$ 个数字 $v_i$ 表示点 $i$ 上的权值。

接下来 $n-1$ 行，每行两个数，$x,y$，表示节点 $x$ 与 $y$ 之间有边。

接下来 $Q$ 行，每一行为一个查询，格式如上所述。

输出格式

对于每一个查询，输出一行，表示满足条件的最大值。

数据范围

$1 \le n,Q \le 10^5$,
$1 \le v_i \le 2^{30}$
查询 $1$ 中 $1 \le y ≤ 2^{30}$，
查询 $2$ 中 $1 \le z ≤ 2^{30}$。

输入样例：

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

输出样例：

7
6
12
11
14