$N$개의 정점으로 이루어진 루트 있는 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있다. $i$번 정점은 가중치 $A_i$를 가지고 있다. 초기에는 $r$번 정점이 루트이다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

• 0 x y: x의 서브트리에 있는 정점들의 가중치를 y로 바꾼다.
• 1 r: 트리의 루트를 r로 바꾼다.
• 2 x y z: x와 y를 잇는 경로에 있는 정점들의 가중치를 z로 바꾼다.
• 3 x: x의 서브트리에 있는 정점들의 가중치의 최솟값을 출력한다.
• 4 x: x의 서브트리에 있는 정점들의 가중치의 최댓값을 출력한다.
• 5 x y: x의 서브트리에 있는 정점들의 가중치를 y만큼 더한다.
• 6 x y z: x와 y를 잇는 경로에 있는 정점들의 가중치를 z만큼 더한다.
• 7 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 최솟값을 출력한다.
• 8 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 최댓값을 출력한다.
• 9 x y: x의 부모를 y로 바꾼다. 만약 x의 서브트리 안에 정점 y가 존재한다면 이 쿼리를 무시한다.
• 10 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 합을 출력한다.
• 11 x: x의 서브트리에 있는 정점들의 가중치의 합을 출력한다.

입력

첫 번째 줄에 두 정수 $N$, $M$ 이 주어진다. ($1 \le N, M \le 10^5$)

이후 $N-1$개의 줄에는 각 간선이 연결하는 두 정점 번호 $u, v$가 주어진다. ($1 \le u, v \le N$)

이후 $N$개의 줄에 $i$번 정점의 가중치 $A_i$ 가 주어진다.

이후 초기 루트의 정점 번호 $r$이 주어진다. ($1 \le r \le N$)

이후 $M$개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

입력으로 주어지는 모든 정수는 C++ int 형으로 표현될 수 있으며, 쿼리를 처리하는 도중, 모든 정점의 가중치의 합이 int 범위를 초과하지 않도록 입력이 주어진다.

출력

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

Sample

Input

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

9
1
1

Sample

Input

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

173
860
103
791
608
1557