Problem Description

You are given a rooted tree with $n$ nodes, each node having a weight. There are $q$ operations, divided into twelve types:

• 0 x y means to change the weights of all nodes in the subtree of $x$ to $y$;
• 1 x means to change the root of the tree to node $x$;
• 2 x y z means to change the weights of all nodes on the simple path from $x$ to $y$ to $z$;
• 3 x means to query the minimum weight in the subtree of $x$;
• 4 x means to query the maximum weight in the subtree of $x$;
• 5 x y means to increase the weights of all nodes in the subtree of $x$ by $y$;
• 6 x y z means to increase the weights of all nodes on the simple path from $x$ to $y$ by $z$;
• 7 x y means to query the minimum weight on the simple path from $x$ to $y$;
• 8 x y means to query the maximum weight on the simple path from $x$ to $y$;
• 9 x y means to change the parent of $x$ to $y$, if $y$ is in the subtree of $x$, ignore this operation;
• 10 x y means to query the sum of weights on the simple path from $x$ to $y$;
• 11 x means to query the sum of weights in the subtree of $x$.

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of nodes and the number of operations, respectively.
The next $n-1$ lines each contain two positive integers $u$ and $v$, indicating an edge between nodes $u$ and $v$.
Following that, $n$ lines each contain one integer representing the weight of each node.
The next line contains one positive integer indicating the initial root of the tree.
Finally, $q$ lines each contain several positive integers representing an operation.

Output Format

For each operation of types 3, 4, 7, 8, 10, and 11, output one line containing one integer as the answer.

Sample Input and Output

Input Sample #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

Output Sample #1

9
1
1

Input Sample #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

Output Sample #2

173
860
103
791
608
1557

Notes

Source: BZOJ 3153

Data Range:

For $100\%$ of the data, $1 \le n, q \le 10^5$, and all intermediate values calculated are within the range $[-2^{31}, 2^{31})$.

Since this problem is too difficult to write, you can download the test data here to test locally before submitting.

见题面 Input 部分

见题面 Output 部分