Một bài toán khác về kỹ thuật Euler Tour 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 trên đường đi từ gốc tới 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ị trên đường đi từ gốc tới 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 4
1 3 2
2 4

Đầu ra:

11
8

Giải thích: Đường đi từ gốc tới nút ~4~ gồm các nút ~1, 3, 4~ với tổng ~4 + 5 + 2 = 11~. Sau khi đổi ~v_3 = 2~, tổng trở thành ~4 + 2 + 2 = 8~.

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~