Today, we'll be practicing modifications on a tree!

Input

The first line contains two integers, $N$ and $M$, denoting that there are $N$ vertices and $M$ queries.

Then there are $N-1$ lines, each line containing two integers $x$ and $y$, denoting that there is an edge between $x$ and $y$ in the tree.

Then there are $N$ more lines, each containing one number: the initial weight of each vertex.

Then the next line contains the root.

Then there are $M$ lines:

The first number is $K$.

$K=0$ means subtree modification. $K$ is followed by $x$ and $y$. This operation sets all vertex weights in the subtree of $x$ to $y$.

$K=1$ means change root. The line contains one additional integer $x$, representing the new root of the tree.

$K=2$ means path modification. $K$ is followed by integers $x,y,z$. This operation sets $z$ as the vertex weight of all vertices on the path from $x$ to $y$.

$K=3$ means subtree min. $K$ is followed by $x$, the root of the queried subtree.

$K=4$ means subtree max. $K$ is followed by $x$, the root of the queried subtree.

$K=5$ means increment subtree. $K$ is followed by $x$ and $y$, the root of the queried subtree and the value to increment by.

$K=6$ means path increment. $K$ is followed by $x,y,z$. This operation increments all vertex weights on the path from $x$ to $y$ by $z$.

$K=7$ means path min. $K$ is followed by $x$ and $y$, the endpoints of the queried path.

$K=8$ means path max. $K$ is followed by $x$ and $y$, the endpoints of the queried path.

$K=9$ means change parent. $K$ is followed by $x$ and $y$. This operation changes the parent of $x$ to $y$. If $y$ is in the subtree of this operation, do nothing.

$K=10$ means path sum. $K$ is followed by $x$ and $y$, and asks for the sum of the weights on the path from $x$ to $y$.

$K=11$ means subtree sum. $K$ is followed by $x$, and asks for the sum of the weights in the subtree root at $x$.

Output

Print an answer for each query. All answers go on their own lines.

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

Sample Output 1

9
1
1

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

Sample Output 2

173
860
103
791
608
1557

Constraints

$N,M\le {10}^5$

All intermediate values can be stored in a C++ int.