Tý cần giải bài toán sau:

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

Đị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\)).
• \(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): \(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.