Tywin Lanister là một thiên tài về chiến thuật. Quân đội của ong ta rất tốt khiến cho ông ta có thể dễ dàng đưa ra các quyết định quan trọng. Quân đội ông ta được tổ chức như một hệ thống cấp bậc trên – dưới (có dạng hình cây). Mỗi quân nhân A báo cáo trực tiếp cho duy nhất một quân nhân B. Chúng ta nói B là cấp trên của A nếu như có một dãy báo cáo bắt đầu bằng A và kết thúc bằng B. Mỗi một quân nhân khi nhập quân đội có một kĩ năng chiến đấu nhất định được đặc trưng bởi một con số.

Mỗi một trận đánh, một quân nhân S được chọn làm lãnh đạo và khi đó S cùng với các quân nhân nhận S làm lãnh đạo sẽ được đi chiến đấu. Kỹ năng chiến đấu của quân đội này là tổng kỹ năng chiến đấu của tất cả các quân nhân tham gia. (Biểu thị bằng truy vấn (Q S). Sau một trận đánh, kỹ năng chiến đấu của một số quân nhân bị thay đổi. Nếu kỹ năng chiến đấu của quân nhân S mang giá trị mới x thì nó thể hiện bằng truy vấn U S x

Bạn nhận được cấu trúc của quân đội với số quân nhân là N, kĩ năng chiến đấu ban đầu của mỗi quân nhân là M truy vấn thay đổi. Với mỗi truy vấn dạnh Q S bạn hãy in ra kỹ năng chiến đấu của nhóm quân nhân tương ứng.

Input:

• Dòng 1: chứa hai số nguyên dương N, M ( 1 ≤ N, M ≤ 105)

• Dòng 2: chứa N số nguyên không âm, số thứ i là kĩ năng chiến đấu ban đầu của quân nhân i, kỹ năng chiến đấu thuộc [0, 20000].

• N – 1¬ dòng tiếp theo, mỗi dòng ghi hai số nguyên u, v thể hiện u phải báo cáo trực tiếp với v hoặc ngược lại.

• M dòng tiếp theo, mỗi dòng thể hiện một truy vấn có một trong hai dạng U S x hoặc Q S ( 1 ≤ S ≤ N)

Output:

Với mỗi truy vấn dạng Q S in ra kỹ năng chiến đấu của nhóm quân do S lãnh đạo.

Sample Input

5 8
7 2 0 5 8
1 2
2 3
2 4
1 5
Q 1
Q 2
U 2 4
Q 1
Q 2
U 5 3
Q 1
Q 2

Sample Output

22
7
24
9
19
9