Maximum XOR Query on Tree

You are given a tree with n nodes numbered from 1 to n, with the root at node 1. Each node i has an associated weight v_i. The tree is undirected and connected. You are also given q queries, which can be of the following two types:

• 1 x z: For query type 1, find the maximum value of v_i \oplus z among all nodes i in the subtree of node x (including x itself). Here, \(\oplus\) denotes the bitwise XOR operation.
• 2 x y z: For query type 2, consider the unique simple path between nodes x and y in the tree. Find the maximum value of v_i \oplus z among all nodes i on that path.

Note: It is guaranteed that the given tree is rooted at node 1, and the tree structure is provided via n-1 edges connecting the nodes.

Input Format: The first line of input contains two integers n and q — the number of nodes in the tree and the number of queries respectively. The second line contains n integers, where the i^th integer denotes v_i, the weight of node i. The next n-1 lines each contain two integers u and v representing an edge between nodes u and v. The following q lines each describe a query in one of the two formats described above.

inputFormat

The first line contains two space-separated integers: n and q.

The second line contains n space-separated integers: v₁, v₂, \dots, v_n.

Each of the next n-1 lines contains two space-separated integers: u and v, denoting an edge in the tree.

Each of the following q lines contains a query in one of the following formats:

• 1 x z
• 2 x y z

outputFormat

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

sample

5 3
3 6 7 4 2
1 2
1 3
2 4
2 5
1 2 5
2 4 3 1
1 1 2

7
7
6