Tý có một tập đoàn công nghệ có \(N\) phòng ban, được tổ chức theo mô hình cây phân cấp (phòng ban \(1\) là trụ sở chính). Các phòng ban được đánh số từ \(1\) đến \(N\), và có \(N-1\) đường truyền dữ liệu nối giữa các phòng ban. Mỗi phòng ban \(i\) có một chỉ số năng suất \(w_i\). Công ty thực hiện \(Q\) thao tác:

• 1 u val: Cập nhật chỉ số năng suất của phòng \(u\) thành \(val\).
• 2 u: Tính tổng chỉ số năng suất của toàn bộ các phòng ban thuộc nhánh cây con gốc \(u\) (bao gồm cả phòng \(u\)).

Hãy viết chương trình quản lý dữ liệu cho tập đoàn.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(w_1, w_2, \dots, w_N\) (\(0 \le w_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả đường truyền dữ liệu.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác.

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra tổng chỉ số năng suất trên một dòng.

Ví dụ

Input:

7 5
2 4 1 3 5 6 8
1 2
1 3
2 4
2 5
3 6
3 7
2 1
1 5 10
2 1

Output:

29
34

Ràng buộc