Trong giờ học về kỹ thuật trải phẳng cây bằng Euler Tour, thầy giáo giao cho các bạn một bài toán như sau:

Cho trước một cây gồm ~n~ nút đánh số từ ~1~, có gốc là nút ~1~. Nút ~i~ mang giá trị ~v_i~. Nhiệm vụ là thực hiện ~q~ truy vấn thuộc hai loại:

1. Đổi giá trị ở nút ~k~ thành ~x~: ~v_k = x~.
2. Tính tổng giá trị các nút nằm trong cây con của nút ~k~.

Per đã tính toán xong nhưng cần các bạn kiểm tra lại cho chính xác. Các bạn hãy giúp đỡ Per nhé!

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n~, ~q~ — tổng số nút và số lượng truy vấn.
• Dòng tiếp theo chứa ~n~ số nguyên ~v_i~ — giá trị của từng nút.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_i~, ~v_i~ — mô tả một cạnh của cây.
• ~q~ dòng tiếp theo, mỗi dòng có một trong hai dạng:
  • ~1~ ~k~ ~x~ — đổi giá trị nút ~k~ thành ~x~;
  • ~2~ ~k~ — hỏi tổng giá trị cây con của nút ~k~.

Kết quả

Với mỗi truy vấn loại ~2~, in ra đáp án trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

8
10

Giải thích: Cây con của nút ~3~ gồm các nút ~3, 4, 5~ với tổng ~5 + 2 + 1 = 8~. Sau khi đổi ~v_5 = 3~, tổng trở thành ~5 + 2 + 3 = 10~.

Giới hạn

• ~1 \le n, q \le 2 \cdot 10^5~
• ~1 \le v_i \le 10^9~
• ~1 \le u_i, v_i \le n~
• Truy vấn loại 1: ~1 \le k \le n~, ~1 \le x \le 10^9~
• Truy vấn loại 2: ~1 \le k \le n~