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