[TJOI2018]异或

题目描述

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