Thầy Trí có một cây với $n$ đỉnh, được đánh số từ $1$ đến $n$. Cây ban đầu có gốc là $1$ và mỗi nút trên cây sẽ được gán một số.

Các em cần thực hiện $3$ loại truy vấn sau:

• "1 v": Đổi nút $v$ thành gốc của cây.
• "2 u v x: Tăng các nút trong cây con nhỏ nhất chứa $u$ và $v$ lên $x$ đơn vị.
• "3 v": Tính tổng tất cả các giá trị trong cây con gốc $v$

Cây con của nút $v$ là tập tất cả nút mà đường đi ngắn nhất từ nó đến gốc phải chứa $v$. Lưu ý cây con của một nút có thể thay đôi nếu đổi gốc của cây.

Dữ liệu vào

• Dòng đầu tiên chứa hai số $n$ và $q$ $(1\le n,q\le {10}^5)$ - là số nút và số lượng truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2...a_n$ $(-{10}^8\le a_i\le {10}^8)$ là các giá trị ban đầu của các nút.
• $n-1$ dòng tiếp theo, mỗi dòng chứa cặp số $u_i,v_i$ $(1\le u_i,v_i\le n)$ mô tả cạnh nối đỉnh $u_i$ đến đỉnh $v_i$ trên cây.
• $q$ dòng tiếp theo mô tả các câu truy vấn

Dữ liệu ra

• In ra kết quả với mỗi truy vấn loại $3$.

Input 1

6 7 
1 4 2 8 5 7 
1 2 
3 1
4 3
4 5 
3 6 
3 1
2 4 6 3
3 4 
1 6 
2 2 4 -5 
1 4 
3 3

Output 1

27 
19 
5

Input 2

4 6 
4 3 5 6 
1 2 
2 3 
3 4 
3 1 1 
3 2 
2 4 3 
1 1 
2 2 4 -3 
3 1

Output 2

18
21