There is a rooted tree consisting of $N$ vertices. The vertices are numbered from $1$ to $N$. Vertex $i$ has a weight $A_i$. Initially, vertex $r$ is the root.

Write a program that processes the following queries:

• 0 x y: Change the weights of all vertices in the subtree of $x$ to $y$.
• 1 r: Change the root of the tree to $r$.
• 2 x y z: Change the weights of all vertices on the path between $x$ and $y$ to $z$.
• 3 x: Print the minimum weight among the vertices in the subtree of $x$.
• 4 x: Print the maximum weight among the vertices in the subtree of $x$.
• 5 x y: Add $y$ to the weights of all vertices in the subtree of $x$.
• 6 x y z: Add $z$ to the weights of all vertices on the path between $x$ and $y$.
• 7 x y: Print the minimum weight among the vertices on the path between $x$ and $y$.
• 8 x y: Print the maximum weight among the vertices on the path between $x$ and $y$.
• 9 x y: Change the parent of $x$ to $y$. If vertex $y$ lies inside the subtree of $x$, ignore this query.
• 10 x y: Print the sum of weights of all vertices on the path between $x$ and $y$.
• 11 x: Print the sum of weights of all vertices in the subtree of $x$.

Input

The first line contains two integers $N$, $M$ ($1 \le N, M \le 10^5$).

The next $N-1$ lines each contain two integers $u$, $v$ ($1 \le u, v \le N$) representing an edge connecting the two vertices.

The next $N$ lines contain the weight $A_i$ of vertex $i$.

The next line contains the initial root vertex $r$ ($1 \le r \le N$).

The next $M$ lines contain queries as described above.

All integers given in the input can be represented by the C++ int type, and the input is given such that the sum of all vertex weights does not exceed the range of int during the processing of the queries.

Output

For each query that produces an output, print the result on a separate line in the order they occur.

Examples

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

Output 1

9
1
1

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

Output 2

173
860
103
791
608
1557