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

#### Input Specification

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

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

Then there are lines, each line containing two integers and , denoting that there is an edge between and in the tree.

Then the next line contains the root.

Then there are lines:

The first number is .

means change root. The line contains one additional integer , representing the new root of the tree.

means path modification. is followed by integers . This operation sets as the vertex weight of all vertices on the path from to .

means path increment. is followed by . This operation increments all vertex weights on the path from to by .

means path min. is followed by and , and asks for the min of the weights on the path from to .

means path max. is followed by and , and asks for the max of the weights on the path from to .

means path sum. is followed by and , and asks for the sum of the weights on the path from to .

means change parent. is followed by and . This operation changes the parent of to . If is in the subtree of this operation, do nothing.

means lowest common ancestor (LCA). is followed by and . This operation queries the LCA of and .

#### Output Specification

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

#### Constraints

#### Subtasks

For 20% of the points, .

For 50% of the points, .

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
```

## Comments