[TJOI2018]异或

题目描述

现在有一颗以 $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$ 异或结果最大值。

输出格式


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

输入输出样例

输入样例 #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\%$ 的数据,保证 $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}$。