Tổng đường đi

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

Bạn cần xử lý hai loại truy vấn sau:

• Cập nhật giá trị của một nút: Thay đổi giá trị của nút \(s\) thành \(x\).
• Tính tổng: Tính tổng giá trị của tất cả các nút trên đường đi từ gốc cây (nút \(1\)) đến nút \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)), lần lượt là số lượng nút và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) (\(1 \le v_i \le 10^9\)), là giá trị ban đầu của các nút.
• \(n-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n\)), cho biết có một cạnh nối giữa hai nút \(a\) và \(b\).

• Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi truy vấn có dạng:

• "1 s x": Thay đổi giá trị của nút \(s\) thành \(x\) (\(1 \le s \le n, 1 \le x \le 10^9\)).

• "2 s": Tính tổng giá trị trên đường đi từ gốc đến nút \(s\) (\(1 \le s \le n\)).

Output

• Với mỗi truy vấn loại 2, in ra tổng giá trị tính được trên một dòng.

Example

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

9
9

Scoring

• Subtask 1 (30 điểm): \(n, q \le 1000\).
• Subtask 2 (70 điểm): Không có ràng buộc gì thêm.