题目描述

现在有一颗以 $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$ 行，每一行为一个查询，格式如上所述。

输出格式

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

样例

input

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

output

7
6
12
11
14

数据范围与提示

对于 $10\%$ 的数据，有 $1 \le n, Q \leq 100$ 。
对于 $20\%$ 的数据，有 $1 \le n, Q \leq 1000$ 。
对于 $40\%$ 的数据，有 $1 \le n, Q \leq 10000$ 。
对于 $100\%$ 的数据，有 $1 \le n, Q \leq 100000$ ，查询 1 中的 $y \leq 2^{30}$ ，查询 2 中的 $z \leq 2^{30}$ 。