B. Depth Range Update
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a tree with $$$n$$$ nodes rooted at $$$1$$$ and an array $$$a$$$ where $$$a_i$$$ is the value of the node $$$i$$$.

We define $$$depth_u$$$ as the number of edges on the shortest path from node $$$u$$$ to node $$$1$$$.

You are to process $$$q$$$ queries of two types:

— $$$1 \: l \: r \: x$$$ : for every node $$$u$$$ that satisfies $$$l \le dpth_u \le r$$$ do the following assignment: $$$a_u := a_u \oplus x$$$, it's guaranteed that $$$r-l = 1$$$ (where $$$\oplus$$$ corresponds to the XOR bitwise operation).

— $$$2 \: u$$$ : print the following sum : $$$\sum_{v \in subtree_u} xorpath(u,v)$$$ , where $$$xorpath(u,v)$$$ is the xor sum of node values on the shortest path between $$$u$$$ and $$$v$$$.

Input

The first line contains one integer $$$t \: (1 \le t \le 100)$$$ — the number of test cases.

The first line of each testcase contains two integers $$$n$$$ and $$$q \: (2 \le n \le 10^5, \: 1 \le q \le 10^5)$$$

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n \: (0 \le a_i \lt 2^{20})$$$.

The next $$$n-1$$$ lines contain the tree edges $$$u \: v$$$ $$$(1 \le u,v \le n)$$$.

The next $$$q$$$ lines contain the queries described above $$$(0 \le l \le r \le n), (r-l = 1)$$$, $$$(0 \le x \lt 2^{20})$$$, $$$(1 \le u \le n)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each query of the second type, print the required sum.

Example
Input
2
4 4
2 3 0 7
2 4
1 3
4 1
2 4
1 0 1 4
1 2 3 6
1 0 1 4
6 1
4 7 7 3 3 3
1 4
4 6
3 5
3 4
6 2
2 2
Output
11
7