Animal City Rescue

You are given a tree with N nodes (numbered 1,2,…,N) representing states in a federation. The tree has N-1 bidirectional roads connecting the states such that the tree is connected.

Each state i contains a machine with an initial weight a_i. When activated, the machine produces energy stones that, per unit time, save a_i carnivores. Nick starts from state X at time 0 and travels along the unique shortest path from X to Y, moving one state per unit time. Upon arriving at any state, he starts its machine. For a query from X to Y, the total number of carnivores saved during the journey is calculated as follows:

Let the path from X to Y be S(X, Y) = [v₀=X, v₁, …, v_k=Y] (with k = dis(X,Y)). For each state v_i on the path, its machine contributes over the journey an amount equal to a_vi × (1 + 2 + ... + (k-i)) (note: if k-i = 0 then the contribution is 0). The answer to the query is the sum of these contributions modulo 20160501.

There are three types of operations:

1. 1 x y w: Upgrade the machines on the shortest path between nodes x and y (including both endpoints) by increasing their weight by w.
2. 2 x y: Answer a query. Let S(x, y) be the set of nodes on the shortest path between x and y. For each node i in S(x, y), if the distance from i to y along this path is L, then its contribution is a_i × (1 + 2 + ... + L). Output the sum of contributions modulo 20160501.
3. 3 x: Roll back the state of all machines to the state after the x-th upgrade operation. (Use x = 0 to revert to the initial state.)

Note: After each upgrade operation (type 1), the current state (i.e. the values of all a_i) is saved. The operations are given online and are encrypted, so you must process them in the order given.

Input/Output Format: See below.

inputFormat

The input begins with two integers N and M.

The next line contains N integers: a₁, a₂, …, a_N indicating the initial weights of the machines.

Then follow N-1 lines, each containing two integers u and v, denoting a bidirectional road between states u and v.

Then follow M lines, each representing an operation. Each operation is in one of the following formats:

• 1 x y w: Upgrade – add w to the weight of every machine on the shortest path between x and y.
• 2 x y: Query – output the number of carnivores saved when Nick travels from x to y with the current state.
• 3 x: Rollback – revert the state of all machines to that after the x-th upgrade operation (x=0 means the initial state).

outputFormat

For each query operation (type 2), output a single line containing the answer modulo 20160501.

sample

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

16
20
16

</p>