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