Tý là quản lý kho lương thực của vương quốc. Vương quốc có \(N\) làng được nối với nhau bởi \(N-1\) con đường tạo thành cấu trúc cây. Mỗi làng i có một số tấn lúa \(a_i\).

Tý cần xử lý \(Q\) truy vấn thuộc hai loại:

• 1 u val: Điều chỉnh số lúa ở làng \(u\) thành \(val\) tấn.
• 2 u: Tính tổng số lúa của toàn bộ nhánh có gốc là làng \(u\) (gồm làng \(u\) và tất cả làng trong vùng phụ cận phía dưới).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và Q (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)). - N-\(1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N\)) mô tả một con đường.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn.

Kết quả ra

• Với mỗi truy vấn loại 2, in ra tổng số lúa của nhánh tương ứng.

Ví dụ

Input

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

Output

14
20
21

Ràng buộc

• Subtask 1 (20 điểm): \(Q \le 100\).
• Subtask 2 (20 điểm): \(Q \le 5000\).
• Subtask 3 (30 điểm): \(Q \le 10^{5}, không có truy vấn cập nhật\).
• Subtask 4 (30 điểm): Không có ràng buộc gì thêm.