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