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).

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

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

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): \(N, Q \le 100\).
• Subtask 2 (20 điểm): \(N, Q \le 5000\).
• Subtask 3 (30 điểm): \(N, 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.