题目描述

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

1. ( 1 \ x \ y )：查询节点 ( x ) 的子树中与 ( y ) 异或结果的最大值。
2. ( 2 \ x \ y \ z )：查询路径 ( x ) 到 ( y ) 上的点与 ( z ) 异或结果的最大值。

输入格式

第一行是两个数字 ( n ) , ( Q )。
第二行是 ( n ) 个数字用空格隔开，第 ( i ) 个数字 ( v_i ) 表示点 ( i ) 上的权值。
接下来 ( n-1 ) 行，每行两个数 ( x, y )，表示节点 ( x ) 与 ( y ) 之间有边。
接下来 ( Q ) 行，每一行为一个查询，格式如上所述。

输出格式

对于每一个查询，输出一行，表示满足条件的最大值。

样例

输入

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% ) 的数据，有 ( 1 \le n, Q \leq 100 )；
对于 ( 20% ) 的数据，有 ( 1 \le n, Q \leq 1000 )；
对于 ( 40% ) 的数据，有 ( 1 \le n, Q \leq 10000 )；
对于 ( 100% ) 的数据，有 ( 1 \le n, Q \leq 100000 )，查询 1 中的 ( y \leq 2^{30} )，查询 2 中的 ( z \leq 2^{30} )。