Description

Note: We provide a formal statement at the end.

Zootopia is a federation with $N$ states, and the federation forms a tree. That is, there are $N-1$ undirected roads connecting the $N$ states, and all $N$ states are connected. The states are numbered $1,2,3,\dots,N$. Each state has exactly one machine. Starting from the moment after a machine is activated, it begins producing energy stones, producing one per unit time. An energy stone takes effect immediately when produced, and in each unit time it can save a certain number of carnivores. The types of energy stones produced by machines in different states may differ: in state $i$, the machine produces energy stones that can save $a_i$ carnivores per unit time.

Nick and Judy do not have much time left, so they decide to split up. Nick starts from state $X$ and heads to state $Y$, traveling along the shortest path from $X$ to $Y$. Nick starts at time $0$ and moves one state every unit time. Each time he arrives at a state, Nick activates the machine there. Nick wants to know, during the time from when he leaves $X$ until he arrives at $Y$, how many carnivores are saved in total. Nick is hesitant about which route to choose, so he will ask you several queries, hoping that you, who are smarter than him, can help.

While he is asking you, the situation in Zootopia is also changing. The Zootopia Federal Security Bureau can perform a modification operation $X,Y,\Delta$: it upgrades the machines in all states on the shortest path from $X$ to $Y$ (including states $X$ and $Y$). After the upgrade, the number of carnivores that the energy stones produced by these machines can save per unit time increases by $\Delta$.

Of course, the sloth Flash will not sit still. He has a monitor that watches the machines in every state. Whenever any machine is upgraded, the monitor saves the current attributes $a_i$ of machines in all states. Flash can use a mysterious weapon to perform a rollback operation $X$, restoring the current machine attributes of all states to the state saved at the $X$-th time (where $X=0$ means the initial state before any upgrade). Note that saving happens only when a modification operation is executed.

Now you are given $M$ operations in order. If an operation is a query, output how many carnivores are saved in total when Nick travels from $X$ to $Y$ under the current situation. Since the answer may be large, you only need to output it modulo $20160501$. Note that all $M$ operations are encrypted.

Formal statement:

You are given a tree with $N$ nodes. Then there are $M$ operations of three types:

• 1 x y w: add $w$ to the node weight of every node on the path from $x$ to $y$.
• 2 x y: a query. Let the set of nodes on the path from $x$ to $y$ be $S(x,y)$, and let the path length between nodes $p,q$ be $\text{dis}(p,q)$. Compute $\sum_{i\in S(x,y)}\sum_{j\le \text{dis}(i,y)}a_i\cdot j$. Output the answer modulo $20160501$.
• 3 x: restore the node weights of the whole tree to the state right after the $x$-th 1 operation.

Online processing is required.

Input Format

The first line contains $2$ integers $N,M$, indicating the number of nodes and the number of operations.

The next $N-1$ lines each contain $2$ integers $u,v$, indicating that there is an edge between $u$ and $v$ in the tree.

The next line contains $N$ integers, the initial values of $a_i$ for the machines in the $N$ states.

The next $M$ lines each start with a number indicating the operation type:

• Type 1: a modification operation, followed by $3$ integers $X',Y',\Delta$.
• Type 2: a query operation, followed by $2$ integers $X',Y'$.
• Type 3: a rollback operation, followed by $1$ integer $X'$.

Here $X',Y'$ are encrypted numbers. The correct values are $X=X' \text{xor lastans},Y=Y' \text{xor lastans}$. Here $\text{lastans}$ is the answer of the previous 2 operation modulo $20160501$; if there has been no 2 operation before, then it equals $0$.

Output Format

For each operation 2, output one line containing the queried answer modulo $20160501$.

5 6
1 2
2 3
3 4
4 5
1 2 3 4 5
1 1 5 2
3 0
1 1 3 2
1 3 4 2
3 2
2 1 5

73

5 4
1 2
1 3
2 4
3 5
1 1 1 2 2
1 1 4 2
2 1 4
3 12
2 13 8

12
4

Hint

Constraints: For all data, $1\le n,m\le 10^5$, $1\le a_i,\Delta\le 10^5$, $1\le x,y\le n$.

For $20\%$ of the data, $n,m\le 2000$.

For another $20\%$ of the data, the tree is a chain and there is no operation 3.

For another $40\%$ of the data, the tree is a chain.

Translated by ChatGPT 5