Cho một cây gồm \(N\) nút. Các nút được đánh số \(1,\ 2,\ldots,\ n\) và nút \(1\) là gốc của cây. Trên mỗi nút có một giá trị.

Nhiệm vụ của bạn là trả lời \(Q\) truy vấn, gồm hai loại:

1. Thay đổi giá trị trên nút \(s\) thành \(x\);
2. Tính tổng các giá trị của cây con có gốc \(s\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\): số lượng nút của cây và số truy vấn.
• Dòng tiếp theo chứa \(N\) số nguyên \(v_1,\ v_2,\ldots,\ v_n\): giá trị của mỗi nút.
• Sau đó là \(n-1\) dòng mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(u,\ v\): nghĩa là tồn tại một cạnh nối giữa hai nút \(u\) và \(v\).
• Cuối cùng là \(Q\) dòng mô tả các truy vấn. Mỗi truy vấn sẽ thuộc một trong hai dạng sau: 1 s x (truy vấn loại \(1\)) hoặc 2 s (truy vấn loại \(2\)).

Output

• In ra câu trả lời cho các truy vấn loại \(2\), đáp án của mỗi truy vấn được in ra trên một dòng.

Ràng buộc

• \(1\leq N,\ Q\leq2\times10^5\);
• \(1\leq u,\ v,\ s\leq N\);
• \(1\leq v_i,\ x\leq10^9\);
• Có \(50\%\) số test chỉ có các truy vấn loại \(2\).

Ví dụ

Sample input

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

Sample output

7
15