Path Subset XOR Sum on a Tree

There is a tree with n nodes. Each node has an integer weight. You are given m operations. Operations are given in order. Each operation can be either a query or a modification.

Query Operation: Given two nodes a and b, consider the unique simple path between a and b. Let S be the multiset (note: nodes are distinct even if weights repeat) of weights of nodes along this path. For every nonempty subset of S, compute the bitwise XOR of its elements. The answer to the query is defined as the sum of these XOR values, taken modulo 10^9+7. This value is called the subset XOR sum.

For example, consider S = {1,2,3}. Its nonempty subsets and their XOR values are:

• {1} : 1
• {2} : 2
• {3} : 3
• {1,2} : 1 ⊕ 2 = 3
• {1,3} : 1 ⊕ 3 = 2
• {2,3} : 2 ⊕ 3 = 1
• {1,2,3} : 1 ⊕ 2 ⊕ 3 = 0

The sum is 1 + 2 + 3 + 3 + 2 + 1 + 0 = 12. It can be shown that the answer is given by the formula:

\[ \text{Answer} = 2^{k-1} \times \Bigl(\bigvee_{x \in S} x\Bigr) \mod (10^9+7), \]

where k is the number of nodes on the path, and \(\bigvee\limits_{x\in S} x\) denotes the bitwise OR of all node weights in S.

Modification Operation: Given two nodes a and b and an integer c, update every node on the unique path between a and b by setting its weight to weight ⊕ c (i.e. perform an XOR with c).

You are to process all operations in order and output the answer for each query.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 200000), the number of nodes in the tree and the number of operations.

The second line contains n integers w₁, w₂, ..., wₙ (0 ≤ wᵢ < 2³¹), where wᵢ is the initial weight of node i.

Then follow n-1 lines, each containing two integers u and v (1 ≤ u, v ≤ n), denoting an edge between nodes u and v.

Then follow m lines describing the operations. Each operation is in one of the following two formats:

• 1 a b — a query operation asking for the subset XOR sum on the path from a to b.
• 2 a b c — a modification operation which applies ⊕ c to every node on the path from a to b (0 ≤ c < 2³¹).

It is guaranteed that the given edges form a tree.

outputFormat

For each query operation, output the resulting subset XOR sum modulo 10^9+7 in one line.

sample

3 3
1 2 3
1 2
2 3
1 1 3
2 2 3 1
1 1 3

12
12

</p>