9610 - 异或

现在有一颗以 1 为根节点的由 n 个节点组成的树，节点从 1 至 n 编号。树上每个节点上都有一个权值 v_i。现在有 q 次操作，操作如下：

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

输入

输入的第一行是两个整数，分别代表结点个数 n 和询问个数 q。

第二行有 n 个整数，第 i 个整数表示点 i 的的权值 v_i。

接下来 n-1 行，每行有两个整数 u, v，表示存在一条连结 u 和 v 的边。

接下来 q 行，每行首先有一个整数 op，代表操作类型。

  • 若 op = 1，则一个空格后有两个整数 x, z，代表查询节点 x 的子树中的节点权值与 z 异或结果的最大值。
  • 若 op = 2，则一个空格后有三个整数 x, y, z，代表查询节点 x 到节点 y 的简单路径上的节点的权值与 z 异或结果最大值。

输出

对于每一个查询，输出一行一个整数代表答案。

样例

输入

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

提示

  • 对于 10\% 的数据，保证 n, q \leq 10^2；
  • 对于 20\% 的数据，保证 n, q \leq 10^3；
  • 对于 40\% 的数据，保证 n, q \leq 10^4；
  • 对于 100\% 的数据，保证 2\leq n, q \leq10^5，1 \leq u, v, x, y \leq n，1 \leq op \leq 2，1 \leq v_i, z \lt 2^{30}。

来源

天津省选

时间限制 3 秒
内存限制 256 MB
讨论 统计
上一题 下一题