题目描述

现在有一颗以 $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\%$ 的数据，保证 $1< 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}$。