Có một cây có gốc gồm $N$ đỉnh. Các đỉnh được đánh số từ 1 đến $N$. Đỉnh $i$ có trọng số $A_i$. Ban đầu, đỉnh $r$ là gốc.

Viết chương trình xử lý các truy vấn sau:

• 0 x y: Thay đổi trọng số của các đỉnh trong cây con của $x$ thành $y$.
• 1 r: Đổi gốc của cây thành $r$.
• 2 x y z: Thay đổi trọng số của các đỉnh trên đường đi giữa $x$ và $y$ thành $z$.
• 3 x: In ra giá trị nhỏ nhất của trọng số các đỉnh trong cây con của $x$.
• 4 x: In ra giá trị lớn nhất của trọng số các đỉnh trong cây con của $x$.
• 5 x y: Cộng thêm $y$ vào trọng số của các đỉnh trong cây con của $x$.
• 6 x y z: Cộng thêm $z$ vào trọng số của các đỉnh trên đường đi giữa $x$ và $y$.
• 7 x y: In ra giá trị nhỏ nhất của trọng số các đỉnh trên đường đi giữa $x$ và $y$.
• 8 x y: In ra giá trị lớn nhất của trọng số các đỉnh trên đường đi giữa $x$ và $y$.
• 9 x y: Đổi cha của $x$ thành $y$. Nếu đỉnh $y$ nằm trong cây con của $x$ thì bỏ qua truy vấn này.
• 10 x y: In ra tổng trọng số của các đỉnh trên đường đi giữa $x$ và $y$.
• 11 x: In ra tổng trọng số của các đỉnh trong cây con của $x$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$, $M$ ($1 \le N, M \le 10^5$).

Sau đó $N-1$ dòng, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) biểu diễn một cạnh nối hai đỉnh.

Sau đó $N$ dòng, dòng thứ $i$ chứa trọng số $A_i$ của đỉnh $i$.

Sau đó là một dòng chứa số nguyên $r$ — đỉnh gốc ban đầu ($1 \le r \le N$).

Sau đó $M$ dòng, mỗi dòng chứa một truy vấn như mô tả ở trên.

Tất cả các số nguyên trong dữ liệu vào đều biểu diễn được bằng kiểu int của C++. Trong quá trình xử lý truy vấn, tổng trọng số của tất cả các đỉnh không vượt quá phạm vi của kiểu int.

Dữ liệu ra

In ra kết quả của mỗi truy vấn (các truy vấn in ra kết quả) trên một dòng riêng biệt, theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ví dụ

Đầu vào 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

Đầu ra 1

9
1
1

Đầu vào 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

Đầu ra 2

173
860
103
791
608
1557