Phước và Tân 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, Phước đã nghĩ ra một thách thức hóc búa để đố Tân và quý đọc giả: Biết rằng, cái cây của Phước 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, Phước 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 Tân trả lời câu hỏi của Phước ứng với từng yêu cầu loại ~2~.

Dữ liệu:

• Dòng đầu tiên gồm số nguyên dương ~n, q~ ~(1 \leq n,q \leq 2.10^5)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~A_i~ ~(1 \leq A_i \leq 10^9)~.
• Mỗi dòng trong ~n-1~ dòng tiếp theo, dòng thứ ~i~ bao gồm ~2~ số nguyên dương ~u~ và ~v~ ~(1 \leq u \neq v \leq 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 \leq type \leq 2)~ biểu thị loại truy vấn:
  • ~type=1~ thì sau đó có ~3~ số nguyên dương ~u, v, c~ ~(1 \leq u \neq v \leq n,\ 1 \leq c \leq 2.10^5)~.
  • ~type=2~ thì sau đó có ~2~ số nguyên dương ~u,c~ ~(1 \leq u \leq n,\ 1 \leq c \leq 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 \leq 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 \leq i \leq n)$.
• Subtask $4$ $(25 \%)$: Không có ràng buộc gì thêm.

Ví dụ

Input

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

4
2
0