Cho một cây gồm \(N\) đỉnh, mỗi đỉnh có giá trị ban đầu.

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

• UPDATE u val: gán giá trị của đỉnh \(u\) thành \(val\).
• QUERY u v: tính tổng giá trị các đỉnh trên đường đi từ \(u\) đến \(v\) (kể cả \(u\) và \(v\)).

Tý và Tèo đang chơi trò chơi trên cây. Hãy giúp họ trả lời các truy vấn.

Định dạng đầu vào

• Dòng 1: hai số nguyên \(N, Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)) là giá trị ban đầu của các đỉnh.
• \(N-1\) dòng tiếp: mỗi dòng gồm \(u, v\) mô tả một cạnh của cây.
• \(Q\) dòng tiếp: mỗi dòng có dạng UPDATE u val hoặc QUERY u v.

Định dạng đầu ra

• Với mỗi truy vấn QUERY, in ra một số nguyên là kết quả.

Ví dụ

Input:

5 4
1 2 3 4 5
1 2
1 3
3 4
3 5
QUERY 4 5
UPDATE 3 10
QUERY 4 5
QUERY 1 2

Output:

12
19
11

Ràng buộc