Tywin Lanister là một thiên tài về chiến thuật. Quân đội của ông ta tổ chức 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 của ông được tổ chức như là 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 đội quân 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 đội quân 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 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 được cho 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 và ~M~ truy vấn thay đổi. Với mỗi truy vấn dạng Q ~S~ bạn hãy in ra kỹ năng chiến đấu của nhóm quân tương ứng.

Chú ý rằng các quân nhân đánh số từ ~1~ đến ~N~ và Tywin mang số hiệu ~1~.

Input

Khởi đầu là hai số nguyên ~N, M~.

Tiếp theo là ~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~.

~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.

Cuối cùng là ~M~ dòng, 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~.

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.

Scoring

• ~1 \le N \le 10^5~

• ~1 \le M \le 10^5~

• Kỹ năng chiến đấu nằm trong khoảng ~[0,20000]~

• ~1 \le S \le N~ với mọi truy vấn

• Lãnh đạo tối cao (Tywin) luôn là ~1~

Sample Input 1

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 1

22
7
24
9
19
9