Tý có một hệ thống kho hàng trực tuyến có \(N\) kho trung tâm được tổ chức dạng cây (kho \(1\) là trung tâm chính). Các kho được đánh số từ \(1\) đến \(N\) và có \(N-1\) tuyến vận chuyển. Mỗi kho \(i\) có giá trị tồn kho \(s_i\). Hệ thống nhận \(Q\) thao tác:

• 1 u v val: Cộng thêm \(val\) vào giá trị tồn kho của tất cả các kho nằm trên tuyến đường từ kho \(u\) đến kho \(v\).
• 2 u v: Tính tổng giá trị tồn kho hiện có trên tuyến đường từ kho \(u\) đến kho \(v\).

Hãy xây dựng chương trình xử lý hiệu quả.

Đị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 \(s_1, s_2, \dots, s_N\) (\(0 \le s_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả tuyến vận chuyển.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác.

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra tổng giá trị tồn kho trên một dòng.

Ví dụ

Input:

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

Output:

7
15

Ràng buộc