A85777.「TJOI2018」异或

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

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

对于 $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}$ 。