In a magical forest, there is a large tree where children often gather.

The tree can be viewed as an undirected connected graph with $n$ nodes and $n - 1$ edges. Each node $i$ initially contains $a_i$ bottles of mineral water.

Majesty lives at the top of the tree. One day, he decides to renovate the tree to make it easier to sort his mineral water bottles after drinking a large amount.

Majesty likes binary operations, so he performs the following three types of operations:

1. Increase the number of mineral water bottles at all nodes at a distance of $1$ from node $x$ by $1$. The distance between two nodes in the tree is defined as the number of edges on the shortest path between them.
2. Drink $v$ bottles of water at node $x$.
3. Query the XOR sum of the number of mineral water bottles at all nodes at a distance of $1$ from node $x$.

Majesty performs $m$ operations in total. You are required to output the answer after each type 3 operation.

Input

The first line contains two positive integers $n$ and $m$, representing the number of nodes in the tree and the number of operations, respectively.

The next $n - 1$ lines each contain two integers, representing an edge connecting two nodes.

The $(n + 1)$-th line contains $n$ integers, where the $i$-th integer represents the initial number of mineral water bottles at node $i$.

The next $m$ lines each start with an integer $opt$, representing the operation type.

If $opt = 1$ or $3$, the next integer is $x$, representing the node index for the operation.

Otherwise, the next two integers are $x$ and $v$, representing the node index and the number of bottles consumed.

Output

For each type 3 operation, output one integer per line representing the answer.

Subtasks

• $30\%$ of the data: $n \le 10^3, m \le 10^3$.
• $60\%$ of the data: $n \le 10^5, m \le 10^5$.
• An additional $10\%$ of the data: There exists a node such that all other nodes are at a distance $\le 1$ from it.
• $100\%$ of the data: $1 \le n \le 5 \times 10^5$, $1 \le m \le 5 \times 10^5$, $0 \le a_i \le 10^5$, $1 \le x \le n$, $opt \in \{1, 2, 3\}$.

It is guaranteed that the number of mineral water bottles at each node is non-negative at all times.

Mineral water bottles are neither dry waste nor wet waste; they are recyclable waste.

Examples

Input 1

3 2
1 2
2 3
1 1 4
1 1
3 2

Output 1

5