There is a tree with $n$ nodes rooted at node 1. Each node $i$ has a weight $v_i$. There are $Q$ operations of the following types:

1 $x$ $y$: Find the maximum XOR sum of a value in the subtree of $x$ and $y$. 2 $x$ $y$ $z$: Find the maximum XOR sum of the path between $x$ and $y$ and $z$.

Input

The first line contains two integers $n, Q$. The second line contains $n$ integers separated by spaces, where the $i$-th integer is the weight $v_i$ of node $i$. The next $n-1$ lines each contain two integers $x, y$, representing an edge between node $x$ and node $y$. The next $Q$ lines each contain a query, as described above.

Output

For each query, output one line containing the maximum value satisfying the condition.

Examples

Input 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

Output 1

7
6
12
11
14

Constraints

For 10% of the data, $1 < n, Q \le 100$. For 20% of the data, $1 < n, Q \le 1000$. For 40% of the data, $1 < n, Q \le 10000$. For 100% of the data, $1 < n, Q \le 100000$. For 100% of the data, in query 1, $y \le 2^{30}$, and in query 2, $z \le 2^{30}$.