Tý có một mạng lưới giao thông nội đô có \(N\) nút giao thông được nối với nhau bởi \(N-1\) con đường (cấu trúc cây). Các nút được đánh số từ \(1\) đến \(N\). Mỗi nút \(i\) có một chỉ số tắc nghẽn \(c_i\) ban đầu. Chính quyền thực hiện \(Q\) yêu cầu:

• 1 u v val: Tăng chỉ số tắc nghẽn của tất cả các nút trên đường đi từ nút \(u\) đến nút \(v\) lên \(val\) đơn vị.
• 2 u: Cho biết chỉ số tắc nghẽn hiện tại của nút \(u\).

Hãy lập trình hỗ trợ quản lý giao thông.

Đị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 \(c_1, c_2, \dots, c_N\) (\(0 \le c_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả con đường nối hai nút.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một yêu cầu.

Định dạng đầu ra

• Với mỗi yêu cầu loại 2, in ra chỉ số tắc nghẽn hiện tại trên một dòng.

Ví dụ

Input:

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

Output:

5
0
5

Ràng buộc