트리와 쿼리 13

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로 바꾼다. 정점 y가 x의 서브트리 안에 있으면 이 쿼리를 무시한다.
• 10 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 합을 출력한다.
• 11 x: x의 서브트리에 있는 정점들의 가중치의 합을 출력한다.

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

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

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

이후 줄에는 초기 루트의 정점 번호 r이 주어진다. (1 ≤ r ≤ N)

이후 M개의 줄에는 위에서 설명한 쿼리가 주어진다.

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

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