Description

There is a tree with $N$ nodes, rooted at node $1$, and each node has a weight. There are $M$ operations of three types:

• Operation $1$: increase the weight of node $x$ by $a$.
• Operation $2$: increase the weight of every node in the subtree rooted at node $x$ by $a$.
• Operation $3$: query the sum of weights of all nodes on the path from node $x$ to the root.

Input Format

The first line contains two integers $N, M$, representing the number of nodes and the number of operations.
The next line contains $N$ integers, representing the initial weights of the nodes.
Each of the next $N-1$ lines contains two positive integers $\mathit{from}, \mathit{to}$, indicating that there is an edge $(\mathit{from}, \mathit{to})$ in the tree.
Then there are $M$ lines, each describing one operation. The first number indicates the type of the operation, followed by the parameters of that operation.

Output Format

For each query operation, output the answer. Print each answer on a new line.

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

6
9
13

Hint

For $100\%$ of the testdata, $1 \le N, M \le 10^5$, and the absolute values of all input numbers do not exceed $10^6$.

Translated by ChatGPT 5