Tý cần giải bài toán sau:

Bé An có một khu vườn cây cảnh gồm \(N\) cây xanh được nối với nhau bởi \(N-1\) lối đi (đảm bảo tồn tại đường đi duy nhất giữa mọi cặp cây). Các cây được đánh số từ \(1\) đến \(N\). Ban đầu, cây thứ \(i\) có giá trị thẩm mỹ là \(a_i\). An thực hiện \(Q\) thao tác thuộc hai loại:

• 1 u val: Thay đổi giá trị thẩm mỹ của cây \(u\) thành \(val\).
• 2 u v: Tính tổng giá trị thẩm mỹ của tất cả các cây nằm trên đường đi từ cây \(u\) đến cây \(v\).

Hãy viết chương trình giúp An tính toán nhanh chó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 \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số \(u, v\) mô tả lối đi nối hai cây.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác như trên.

Định dạng đầu ra

• Với mỗi thao tác loại 2, in ra tổng giá trị thẩm mỹ tìm được trên một dòng.

Ví dụ

Input:

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

Output:

12
18

Ràng buộc