Trong khoa học máy tính, cây là một tập hợp các nút được liên kết với nhau theo quan hệ cha-con. Vì tính chất mỗi nút con chỉ có một nút cha và tùy thuộc vào nút gốc được chọn trong cây mà mối quan hệ cha con này mới được hình thành. Hai nút có thể là cha con với nhau nếu như nút \(u\) được chọn làm nút gốc nhưng nếu ta chọn một nút \(v\) khác làm nút gốc thì tính chất này có thể sẽ bị đảo ngược lại và không được cố định...

Tiếng giảng bài khô khan của thầy Tí truyền qua đầu Tí rồi tan vào hư vô. Suốt một buổi học kéo dài \(3\) tiếng về đồ thị, đọng lại trong Tí chỉ là một chữ "cây". Cây là gì? Tí không liệt môn Sinh mà ngược lại còn đạt giải học sinh giỏi quốc gia môn Sinh nữa. Không lẽ \(1\) cái cây mà Tí không biết nó là gì?

Trong sự bực bội, Tí lỡ tay làm rớt cây bút xuống đất. Cậu liền nhanh tay cúi xuống nhặt cây bút lên, xong cũng đưa cặp mắt lên bảng thật nhanh để thầy không chú ý. Nhưng kỳ lạ thay, cái bảng lúc nãy còn trống không bây giờ đã có một cái cây to đùng trên đó. Cây này nó rất lạ nhưng lạ hơn là có chữ "Bài tập về nhà".

Cây trên bảng có \(n\) đỉnh và \(n - 1\) cạnh. Mỗi đỉnh \(i\) mang một giá trị \(v_{i}\). Bên dưới là \(q\) truy vấn liên quan đến cây được thầy Tí viết lên bảng như sau:

• \(1\) \(v\): đổi nút gốc của cây thành nút \(v\).
• \(2\) \(u\) \(v\) \(x\): Với mỗi nút trong cây con có độ lớn nhỏ nhất chứa cả nút \(u\) và \(v\). Hãy tăng giá trị của các nút trong cây con đó thêm \(x\).
• \(3\) \(v\): Tính tổng giá trị của cây con gốc \(v\).

Cây con của đỉnh \(v\) là tập hợp các đỉnh sao cho \(v\) nằm trên đường đi ngắn nhất từ đỉnh này đến gốc của cây.

Hãy giúp Tí giải bài tập về nhà của thầy cho.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(q\) \((1 \leq n, q \leq 10^{5})\) lần lượt là số nút của cây và số truy vấn thầy Tí đưa.
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3}, \ldots, a_{n}\) \((-10^{8} \leq a_{i} \leq 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 hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n, u \neq v)\) biểu diễn một cạnh của cây có nối từ đỉnh \(u\) tới đỉnh \(v\).
• \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi truy vấn thuộc một trong ba dạng như sau:
  • \(1\) \(v\) (\(1 \le v \le n\)): Thể hiện truy vấn loại \(1\).
  • \(2\) \(u\) \(v\) \(x\) (\(1 \le u, v \le n, -10^8 \le x \le 10^8\)): Thể hiện truy vấn loại \(2\).
  • \(3\) \(v\) (\(1 \le v \le n\)): Thể hiện truy vấn loại \(3\).

Output

• Với mỗi truy vấn loại \(3\), in ra một dòng là kết quả của truy vấn đó.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, q \leq 5000\).
• Subtask \(2\) (\(15\%\) số điểm): mỗi đỉnh có tối đa hai cạnh kết nối với đỉnh đó.
• Subtask \(3\) (\(15\%\) số điểm): không có truy vấn loại \(1\).
• Subtask \(4\) (\(15\%\) số điểm): không có truy vấn loại \(2\).
• Subtask \(5\) (\(20\%\) số điểm): trong các truy vấn loại \(2\): \(u = v\).
• Subtask \(6\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

12
19
-10