Jamie and Tree

Description:

Input:

The first line of input contains two space-separated integers n and q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵) — the number of vertices in the tree and the number of queries to process respectively.

The second line contains n space-separated integers a₁, a₂, ..., a_n ( - 10⁸ ≤ a_i ≤ 10⁸) — initial values of the vertices.

Next n - 1 lines contains two space-separated integers u_i, v_i (1 ≤ u_i, v_i ≤ n) describing edge between vertices u_i and v_i in the tree.

The following q lines describe the queries.

Each query has one of following formats depending on its type:

1 v (1 ≤ v ≤ n) for queries of the first type.

2 u v x (1 ≤ u, v ≤ n,  - 10⁸ ≤ x ≤ 10⁸) for queries of the second type.

3 v (1 ≤ v ≤ n) for queries of the third type.

All numbers in queries' descriptions are integers.

The queries must be carried out in the given order. It is guaranteed that the tree is valid.

Output:

For each query of the third type, output the required answer. It is guaranteed that at least one query of the third type is given by Jamie.

Sample Input:

6 7
1 4 2 8 5 7
1 2
3 1
4 3
4 5
3 6
3 1
2 4 6 3
3 4
1 6
2 2 4 -5
1 4
3 3

Sample Output:

27
19
5

Sample Input:

4 6
4 3 5 6
1 2
2 3
3 4
3 1
1 3
2 2 4 3
1 1
2 2 4 -3
3 1

Sample Output:

18
21

Note:

The following picture shows how the tree varies after the queries in the first sample.