Migrated from Lutece 2754 采果子

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

汪次郎种下了一棵以 $1$ 为根节点的树。

现在树上长出了一些果子，每个节点的权值为 $v_i$

现在汪次郎想把果子采摘下来，但是它手上只有一个特殊的机器，这个机器你每次可以输入一个参数 $op$ ，代表执行一个操作。

若 $op=1$，则机器需要输入两个整数 $x,z$，然后机器将会查询节点 $x$ 的子树中的节点权值与 $z$ 异或结果的最大值，并执行一次采摘。 若 $op=2$，则机器需要输入三个整数 $x, y, z$，然后机器将会采摘从节点 $x$ 到节点 $y$ 的简单路径上的节点的权值与 $z$ 异或结果最大值，并执行一次采摘。

汪次郎对这个机器十分好奇，他想知道每次操作得到的结果，你能实现一个程序来帮助他吗？

Input

输入的第一行是两个整数，分别代表结点个数 $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$ 异或结果最大值。

Output

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

Samples

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

Constraints

$1 \leq n,q \leq 10^5$

$1 \leq u, v, x, y \leq n$

$1 \leq op \leq 2$

$1 \leq z ,v_i < 2^{30}$

Resources

2022 UESTC ICPC Training for Data Structures