Tree Query Operations

You are given a tree with (N) nodes numbered from 1 to (N), where the tree is connected and acyclic. Each node has an initial value. The tree is rooted at node 1 for the purpose of subtree queries. You need to support the following operations:

1. Operation 1: 1 x y z (\rightarrow) Add an integer (z) to each node on the unique (shortest) simple path between nodes (x) and (y) (inclusive).

2. Operation 2: 2 x y (\rightarrow) Query the sum of the values of all nodes on the path from (x) to (y) (inclusive).

3. Operation 3: 3 x z (\rightarrow) Add an integer (z) to every node in the subtree of node (x) (where the subtree is defined considering node 1 as the root).

4. Operation 4: 4 x (\rightarrow) Query the sum of the values of all nodes in the subtree of node (x) (including (x) itself).

The input format is described below. Make sure your solution can process all queries efficiently.

inputFormat

The first line contains two integers (N) and (Q) ( (1 \le N, Q \le 10^5)), representing the number of nodes and the number of queries respectively.
The second line contains (N) integers, representing the initial value at each node from 1 to (N).
The next (N-1) lines each contain two integers (u) and (v) denoting an undirected edge between nodes (u) and (v) (forming a tree).
The following (Q) lines each describe a query in one of the following four formats:

• 1 x y z
• 2 x y
• 3 x z
• 4 x

It is guaranteed that the queries are valid.

outputFormat

For each query of type 2 and type 4, output the resulting sum on a separate line.

sample

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

10
14
20