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

Input Specification

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

Then there are ~N~ integers on the next line, each containing one number: the initial weight of each vertex.

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 the next line contains the root.

Then there are ~M~ lines:

The first number is ~K~.

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

~K=1~ 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=2~ 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=3~ means path min. ~K~ is followed by ~x~ and ~y~, and asks for the min of the weights on the path from ~x~ to ~y~.

~K=4~ means path max. ~K~ is followed by ~x~ and ~y~, and asks for the max of the weights on the path from ~x~ to ~y~.

~K=5~ 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=6~ 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=7~ means lowest common ancestor (LCA). ~K~ is followed by ~x~ and ~y~. This operation queries the LCA of ~x~ and ~y~.

Output Specification

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

Constraints

~1 \le N,M \le 10^5~

~1 \le x,y \le N~

Subtasks

For 20% of the points, ~K \notin \{0, 1, 2, 6\}~.

For 50% of the points, ~K \notin \{0, 6\}~.

All intermediate values can be stored in a signed 32-bit integer.

Sample Input 1

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

Sample Output 1

1
3
6
17

Sample Input 2

9 13
100 2 1 3 6 5 4 7 8
1 2
1 3
2 4
2 7
3 6
3 8
3 5
5 9
1
1 1 2 101
2 2 2 101
3 8 5
7 9 4
7 3 8
0 4
7 4 7
0 5
7 1 5
6 9 8
5 6 9
3 8 5
4 4 6

Sample Output 2

1
1
3
4
5
21
1
202