Vua An quyết định tăng lương cho toàn bộ quan lại trong cùng một nhánh hành chính. Vương quốc có \(N\) làng, các 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ức lương khởi điểm \(a_i\).

Nhà vua đưa ra \(Q\) chỉ thị thuộc hai loại:

• 1 u val: Tăng lương cho tất cả quan lại trong nhánh gốc \(u\) thêm \(val\) tấn lúa.
• 2 u: Hỏi mức lương hiện tại của quan lại ở làng \(u\).

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\)).
• \(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 mức lương hiện tại của làng \(u\).

Ví dụ

Input

5 5
10 20 30 40 50
1 2
2 3
2 4
1 5
1 2 5
2 1
2 3
1 4 3
2 3

Output

10
25
25

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.