有一个由 $N$ 个顶点组成的有根树。顶点编号为 $1$ 到 $N$。第 $i$ 个顶点有一个权值 $A_i$。初始时，根节点为 $r$ 号顶点。

编写一个程序处理以下查询：

• 0 x y：将 $x$ 的子树中所有顶点的权值改为 $y$。
• 1 r：将树的根节点改为 $r$。
• 2 x y z：将 $x$ 到 $y$ 的路径上所有顶点的权值改为 $z$。
• 3 x：输出 $x$ 的子树中所有顶点权值的最小值。
• 4 x：输出 $x$ 的子树中所有顶点权值的最大值。
• 5 x y：将 $x$ 的子树中所有顶点的权值加上 $y$。
• 6 x y z：将 $x$ 到 $y$ 的路径上所有顶点的权值加上 $z$。
• 7 x y：输出 $x$ 到 $y$ 的路径上所有顶点权值的最小值。
• 8 x y：输出 $x$ 到 $y$ 的路径上所有顶点权值的最大值。
• 9 x y：将 $x$ 的父节点改为 $y$。如果顶点 $y$ 在 $x$ 的子树内，则忽略该查询。
• 10 x y：输出 $x$ 到 $y$ 的路径上所有顶点权值的和。
• 11 x：输出 $x$ 的子树中所有顶点权值的和。

输入

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 10^5$）。

接下来 $N-1$ 行，每行包含两个整数 $u, v$，表示一条边连接的两个顶点编号（$1 \le u, v \le N$）。

接下来 $N$ 行，每行包含一个整数 $A_i$，表示第 $i$ 个顶点的权值。

接下来一行包含一个整数 $r$，表示初始根节点的编号（$1 \le r \le N$）。

接下来 $M$ 行，每行一个查询，格式如上所述。

输入中所有整数均可用 C++ int 类型表示，并且在处理查询的过程中，所有顶点的权值之和不会超出 int 范围。

输出

对于每个查询，按顺序每行输出一个结果。

样例

输入格式 1

5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1

输出格式 1

9
1
1

输入格式 2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

输出格式 2

173
860
103
791
608
1557