【题目描述】

Jamie 给你一棵有 $n$ 个结点的树，结点编号为 $1$ 到 $n$。一开始，树的根为结点 $1$，并且每个结点都有一个初始权值。

现在需要按顺序处理 $q$ 个操作，共有三种类型：

• 1 v：把当前树根改为结点 $v$；
• 2 u v x：找到包含结点 $u$ 和结点 $v$ 的最小子树，并将这棵子树中所有结点的权值加上 $x$；
• 3 v：询问在当前根下，结点 $v$ 的子树中所有结点权值之和。

这里，当前根发生变化后，一个结点的子树也会随之改变。对于当前根 $r$，结点 $v$ 的子树定义为所有满足“从该结点到当前根的简单路径经过 $v$”的结点集合。

请准确处理所有操作。

【输入格式】

第一行输入两个整数 $n,q$，表示结点数和操作数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个结点的初始权值。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树上的一条无向边。

接下来 $q$ 行，每行表示一次操作，格式为：

• 1 v
• 2 u v x
• 3 v

操作按输入顺序依次执行。

【输出格式】

对于每个第三类操作，输出一行一个整数，表示对应查询的答案。保证至少存在一个第三类操作。

【样例输入 #1】

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

【样例输出 #1】

27
19
5

【样例输入 #2】

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

【样例输出 #2】

18
21

【提示】

数据范围：$1 \le n,q \le 10^5$，$-10^8 \le a_i,x \le 10^8$，$1 \le u_i,v_i,u,v \le n$。输入保证给出的图是一棵合法的树。