Nguồn: https://cses.fi/problemset/task/1137

Cho một cây gồm n đỉnh và n - 1 cạnh, các đỉnh được đánh số từ 1 đến n và gốc của cây là 1. Mỗi đỉnh có một giá trị.

Nhiệm vụ của bạn là thực hiện các truy vấn có dạng sau.

1. Thay đổi giá trị của đỉnh s thành x.
2. Tính tổng giá trị các đỉnh con của s.

Input

• Dòng đầu tiên chứa 2 số nguyên n và q ~(1 \leq n, q \leq 2.10^5)~: số lượng đỉnh và số lượng truy vấn.
• Dòng tiếp theo có n số nguyên ~v_1~, ~v_2~, ..., ~v_n~ ~(1 \leq v_i \leq n)~ : giá trị của từng đỉnh.
• n - 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên a ,b ~(1 \leq a, b \leq n)~ chỉ định 1 cạnh của cây giữa đỉnh a và đỉnh b.
• q dòng tiếp theo mỗi dòng sẽ thuộc một trong 2 dạng "1 s x" hoặc "2 s". ~(1 \leq s \leq n)~ ~(1 \leq x \leq 10^9)~

Output

• In ra kết quả với mỗi truy vấn loại 2.

Sample Input 1

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

Sample Output 1

8
10