Tý có một khu bảo tồn thiên nhiên có \(N\) trạm kiểm lâm được kết nối bởi \(N-1\) đường mòn (cấu trúc cây). Các trạm được đánh số từ \(1\) đến \(N\). Mỗi trạm \(i\) có một chỉ số đa dạng sinh học \(d_i\). Kiểm lâm viên thực hiện \(Q\) thao tác:

• 1 u val: Cập nhật chỉ số đa dạng sinh học của trạm \(u\) thành \(val\).
• 2 u v: Tính tổng chỉ số đa dạng sinh học trên đường đi từ trạm \(u\) đến trạm \(v\).
• 3 u: Tính tổng chỉ số đa dạng sinh học của toàn bộ các trạm thuộc nhánh con gốc \(u\).

Hãy viết chương trình hỗ trợ kiểm lâm viên.

Đị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 \(d_1, d_2, \dots, d_N\) (\(0 \le d_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả đường mò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 hoặc 3, in ra kết quả trên một dòng.

Ví dụ

Input:

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

Output:

22
11
27
16

Ràng buộc