Description

There is a tree with $n$ nodes, rooted at $1$, with nodes numbered from $1$ to $n$. Each node $i$ has a value $v_i$. There are $q$ operations as follows:

• $1~x~z$: Query the maximum value of $v \oplus z$ among nodes in the subtree of node $x$.
• $2~x~y~z$: Query the maximum value of $v \oplus z$ among nodes on the simple path from node $x$ to node $y$.

Input Format

The first line contains two integers $n$ and $q$, representing the number of nodes and the number of queries.

The second line contains $n$ integers, where the $i$-th integer is the value $v_i$ of node $i$.

Each of the next $n-1$ lines contains two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

Each of the next $q$ lines starts with an integer $op$, indicating the type of operation.

• If $op = 1$, then it is followed by two integers $x, z$, representing a query for the maximum value of $v \oplus z$ among nodes in the subtree of node $x$.
• If $op = 2$, then it is followed by three integers $x, y, z$, representing a query for the maximum value of $v \oplus z$ among nodes on the simple path from node $x$ to node $y$.

Output Format

For each query, output a single integer on one line representing the answer.

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

Hint

Constraints

• For $10\%$ of the testdata, $n, q \leq 10^2$.
• For $20\%$ of the testdata, $n, q \leq 10^3$.
• For $40\%$ of the testdata, $n, q \leq 10^4$.
• For $100\%$ of the testdata, $2 \leq n, q \leq 10^5$, $1 \leq u, v, x, y \leq n$, $1 \leq op \leq 2$, $1 \leq v_i, z \lt 2^{30}$.

Translated by ChatGPT 5