Tuấn và Kiệt có sở thích treo các quả bóng đơn sắc lên trên cây thông để trang trí. Trong lúc treo, Tuấn đã nghĩ ra một thách thức hóc búa để đố Kiệt và quý độc giả: Biết rằng, cái cây của Tuấn có n đỉnh và n - 1 cạnh nối, gốc của cây là đỉnh 1, mỗi đỉnh có một giá trị là ~A_i~ và chỉ có thể treo duy nhất một quả bóng tại đó. Ban đầu, chưa có quả bóng nào được treo, Tuấn lần lượt đưa ra q yêu cầu, mỗi yêu cầu thuộc 1 trong 2 loại sau:

• 1 u v c: Treo quả bóng có màu c vào các đỉnh chưa có bóng nằm trên đường đi từ u tới v.
• 2 u c: In ra tổng giá trị của các đỉnh nằm trong cây con gốc u treo quả bóng có màu là c.

Nhiệm vụ của bạn: Hãy giúp Kiệt trả lời câu hỏi của Tuấn ứng với từng yêu cầu loại 2.

Dữ liệu: Nhập từ bàn phím:

• Dòng đầu tiên gồm số nguyên dương n, q (1 ~\le~ n, q ~\le~ 2.~10^5~)
• Dòng tiếp theo gồm n số nguyên dương ~A_i~ (1 ~\le~ ~A_i~ ~\le~ ~10^9~).
• Mỗi dòng trong n - 1 dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương u và v (1 ~\le~ u ~\ne~ v ~\le~ n) tồn tại cạnh nối giữa u và v trong cây.
• Mỗi dòng trong q dòng tiếp theo, chứa số đầu tiên là type (1 ~\le~ type ~\le~ 2) biểu thị loại truy vấn:
  • type = 1 thì sau đó có 3 số nguyên dương u, v, c (1 ~\le~ u ~\ne~ v ~\le~ n, 1 ~\le~ c ~\le~ 2.~10^5~).
  • type = 2 thì sau đó có 2 số nguyên dương u, c (1 ~\le~ u ~\le~ n, 1 ~\le~ c ~\le~ 2.~10^5~).

Kết quả:

• Gồm nhiều dòng, mỗi dòng là câu trả lời tương ứng với từng yêu cầu loại 2.

Subtask:

• Subtask 1 (25%): n, q ~\le~ 5000.
• Subtask 2 (25%): Tất cả truy vấn loại 1 đều đứng trước tất cả truy vấn loại 2.
• Subtask 3 (25%): Tồn tại cạnh nối giữa i và i - 1 (2 ~\le~ i ~\le~ n).
• Subtask 4 (25%): Không có ràng buộc gì thêm.

Ví dụ:

Input 1

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

Output 1

4
2
0