Output 2

17

Note

In the second example, coloring nodes 1 and 2 yields the maximum profit.

Constraints

For 30% of the data, $N \le 20$. For 50% of the data, $N \le 100$. For 100% of the data, $0 \le K \le N$.

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

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

Input

The first line contains two integers $N$ and $M$, representing the number of nodes and the number of operations. The next line contains $N$ integers, representing the initial weights of the nodes. The next $N-1$ lines each contain two positive integers $fr$ and $to$, representing an edge between $fr$ and $to$ in the tree. The next $M$ lines each describe an operation. The first number indicates the type of operation (1-3), followed by the parameters for that operation ($x$ or $x$ $a$).

Output

For each query operation, output the answer. Separate the answers with newlines.

Constraints

For 30% of the data, $N, M \le 1000$. For 50% of the data, $N, M \le 100000$ and the data is random. For 100% of the data, $N, M \le 100000$, and the absolute value of all input data will not exceed $10^6$.

Examples

Input 1

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

Output 1

6
9
13