Migrated from Lutece 3130 香味鸡丝

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：带换根的树剖

别忘了，如今我也是个圣堂武士了

——香味鸡丝凯拉克斯

凯拉克斯要训练一批太阳引导员，为此他设计一种树形结构，希望你能实现一些功能。

现给出一棵 $n$ 个节点的有根树，初始根节点为 $1$，标号为 $1$ ~ $n$，你需要维护以下三种操作：

• ① 给定一个点$v$，将整颗树的根变为 $v$。
• ② 给定两个点$u,v$和整数$x$，将lca($u, v$)为根的子树的所有点的点权都加上x。
• ③ 给定一个点$v$，你需要回答以v所在的子树的所有点的权值和。

Input

第一行输入包含两个整数 $n$ 和 $q$ ($1\le n\le 10^5$, $1\le q\le 10^5$) ——分别表示树中的顶点数和要处理的操作数。 第二行包含$n$个空格分隔的整数$a_1, a_2，… , a_n$ ( $-10^8\le a_i\le 10^8$ )表示顶点初始值。 接下来的 $n-1$ 行每行包含两个整数$u_i, v_i$表示顶点$u_i$和$v_i$之间存在无向边;

下面的$q$行代表操作，每个操作根据其类型具有以下格式之一: 对于第一类操作，输入$1$ $v$ ($1\le v\le n$)。 对于第二类操作，输入$2$ $u$ $v$ $x$ ($1\le u,v\le n$，$-10^8\le x\le 10^8$)。 对于第三类操作，输入$3$ $v$ ($1\le v\le n$)。 操作必须按照给定的顺序执行！！！

Output

对于每一次第三类操作，输出权值和的答案。

Samples

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

27
19
5

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

18
21

Note

可以保证至少有一次第三类操作

Resources

2024 UESTC ICPC Training for Data Structure