CF916E.Jamie and Tree

To your surprise, Jamie is the final boss! Ehehehe.

Jamie has given you a tree with n vertices, numbered from 1 to n. Initially, the root of the tree is the vertex with number 1. Also, each vertex has a value on it.

Jamie also gives you three types of queries on the tree:

1 v — Change the tree's root to vertex with number v.

2 u v x — For each vertex in the subtree of smallest size that contains u and v, add x to its value.

3 v — Find sum of values of vertices in the subtree of vertex with number v.

A subtree of vertex v is a set of vertices such that v lies on shortest path from this vertex to root of the tree. Pay attention that subtree of a vertex can change after changing the tree's root.

Show your strength in programming to Jamie by performing the queries accurately!

令你惊讶的是，杰米（Jamie）才是最终 Boss！嘿嘿嘿。

杰米给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。初始时，树的根节点为编号为 $1$ 的顶点。此外，每个顶点上都有一个权值。

杰米还给出了树上的三类查询操作：

1. 1 v —— 将树的根节点更改为编号为 $v$ 的顶点。

2. 2 u v x —— 对同时包含 $u$ 和 $v$ 的最小大小子树中的每个顶点，将其权值增加 $x$。

3. 3 v —— 查询编号为 $v$ 的顶点的子树中所有顶点的权值之和。

顶点 $v$ 的子树定义为：满足 $v$ 位于该顶点到树根的最短路径上的所有顶点构成的集合。请注意：在更改树根后，任意顶点的子树可能发生变化。

向杰米展现你的编程实力，准确执行这些查询操作吧！

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

The second line contains n space-separated integers _a_1, _a_2, ..., a__n ( - 108 ≤ a__i ≤ 108) — 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,  - 108 ≤ x ≤ 108) 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.

输入的第一行包含两个用空格分隔的整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）——分别表示树中顶点的数量以及需要处理的查询数量。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$-10^8 \leq a_i \leq 10^8$）——表示各顶点的初始值。

接下来的 $n-1$ 行每行包含两个用空格分隔的整数 $u_i, v_i$（$1 \leq u_i, v_i \leq n$），描述树中顶点 $u_i$ 与 $v_i$ 之间的一条边。

随后的 $q$ 行描述各个查询。

每个查询根据其类型具有以下格式之一：

• 类型 1：1 v（$1 \leq v \leq n$）；
• 类型 2：2 u v x（$1 \leq u, v \leq n$，$-10^8 \leq x \leq 10^8$）；
• 类型 3：3 v（$1 \leq v \leq n$）。

所有查询中的数字均为整数。

查询必须按给定顺序依次执行。保证输入的树是合法的。

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.

对于每个第三种类型的查询，输出所需的答案。保证 Jamie 至少会给出一个第三种类型的查询。

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

下图展示了第一个样例中查询操作后树的变化情况。