Problem Description

There is a big tree in a magic forest, and children often hold gatherings under it.

The tree can be seen as an undirected connected graph with $n$ nodes and $n - 1$ edges. Each node of the tree has some bottles of mineral water. Initially, node $i$ has $a_i$ bottles.

Majies lives at the top of the tree. One day, he wants to remodel the tree so that it will be convenient for him to sort the empty mineral water bottles for recycling after he drinks a lot of water.

Majies likes binary operations, so he will perform the following three types of operations:

1. Add $1$ to the number of mineral water bottles on every node whose distance to a node $x$ is $1$. The distance between two nodes on 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 numbers of mineral water bottles on all nodes whose distance to a node $x$ is $1$.

Majies has $m$ operations in total. You need to output the answer after each operation of type $3$.

Input Format

The first line contains two positive integers $n, m$, which represent the number of nodes in the tree and the number of queries.

Lines $2$ to $n$ each contain two integers, indicating an edge connecting these two nodes.

Line $n + 1$ contains $n$ integers. The $i$-th integer indicates the initial number of mineral water bottles at node $i$.

Lines $n + 2$ to $n + m + 1$ each start with an integer $opt$ representing the operation type.

If $opt = 1$ or $opt = 3$, then an integer $x$ follows, indicating the node that Majies operates on.

Otherwise, two integers $x, v$ follow, indicating the node that Majies operates on and the number of bottles he drinks.

Output Format

For each operation of type $3$, output one line containing one integer, which is the answer.

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

5

Hint

Idea: dangxingyu, Solution: dangxingyu, Code: dangxingyu, Data: dangxingyu.

For $30\%$ of the testdata, $n \le 10^3$, $m \le 10^3$.

For $60\%$ of the testdata, $n \le 10^5$, $m \le 10^5$.

For another $10\%$ of the testdata, there exists a node such that the distance from every node to this node is $\le 1$.

For $100\%$ of the testdata, $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 any time.

Friendly reminder: mineral water bottles are neither dry waste nor wet waste; they are recyclable waste.

Translated by ChatGPT 5