Bảy viên ngọc rồng

Trái Đất đang bị đe dọa bởi một thế lực bí ẩn đến từ hành tinh Makyo. Để cứu lấy hành tinh, Son Goku và đồng đội phải thu thập 7 viên ngọc rồng đang nằm rải rác trong cây Thần---một cây khổng lồ có nguồn năng lượng vô hạn.

Cây Thần có \(n\) nút (tượng trưng cho các cành cây), được đánh số từ \(1\) đến \(n\), trong đó nút \(1\) chính là gốc. Mỗi nút chứa một nguồn năng lượng khác nhau. Để tìm ra viên ngọc rồng cuối cùng, bạn cần xử lý các loại truy vấn đặc biệt:

• Truy vấn loại 1 (1 s x): Thay đổi năng lượng của một cành cây \(s\) thành \(x\).
• Truy vấn loại 2 (2 s): Tính tổng năng lượng của toàn bộ cây con có gốc tại cành \(s\).

Bằng cách điều chỉnh năng lượng và tìm kiếm, bạn sẽ giúp Goku tìm ra viên ngọc rồng cuối cùng trước khi bọn Makyo tấn công!

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^5)\) --- số lượng nút trên cây Thần và số truy vấn.
• Dòng tiếp theo chứa \(n\) số nguyên \(v_1, v_2, ..., v_n\) \((1 \leq v_i \leq 10^9)\), lần lượt là năng lượng khởi đầu của từng nút.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\), mô tả một đường liên kết giữa hai cành cây.

• \(q\) dòng cuối cùng mô tả các truy vấn, có hai dạng:

• 1 s x --- Thay đổi năng lượng của cành \(s\) thành \(x\) \((1 \leq s \leq n, 1 \leq x \leq 10^9)\).

• 2 s --- Tính tổng năng lượng của cây con có gốc tại cành \(s\) \((1 \leq s \leq n)\).

Output

• Đối với mỗi truy vấn loại 2 s, in ra một số nguyên --- tổng năng lượng của cây con có gốc tại cành \(s\).

Example

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

8
10

Scoring

• Có \(70\%\) số test tương ứng với \(70\%\) số điểm có \(n, q \leq 1000\)
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 2.10^5\).