Tý muốn tính tổng số lúa trên tuyến đường vận chuyển từ thủ đô (làng 1) đến một làng bất kỳ. 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ột kho lương \(a_i\).

Có \(Q\) truy vấn thuộc hai loại:

• 1 u val: Cập nhật số lúa ở làng \(u\) thành \(val\) tấn.
• 2 u: Tính tổng số lúa trên đường đi từ thủ đô (làng 1) đến làng \(u\) (bao gồm cả hai đầ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 tổng số lúa trên đường từ gốc đến làng \(u\).

Ví dụ

Input

5 5
3 5 2 7 1
1 2
2 3
2 4
1 5
2 3
1 4 10
2 4
2 5

Output

10
15
16

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.