Comet OJ

C0656 [TJOI2018]xor

内存限制：256 MB 时间限制：3000 ms

题目描述

现在有一颗以 $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

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

样例输出 1

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