Cho một đồ thị dạng cây gồm có ~n~ đỉnh (đánh số từ ~0~ đến ~n-1~) được kết nối bởi ~n-1~ cạnh, cạnh thứ ~i~ có trọng số ~w_i~. Lần lượt các cạnh được đánh số từ ~1~ đến ~n-1~ theo thứ tự xuất hiện trong dữ liệu vào.

Thực hiện ~m~ thao tác thuộc một trong ba dạng sau:

• C ~i~ ~x~: Thay đổi trọng số của cạnh thứ ~i~ thành giá trị ~x~;

• N ~u~ ~v~: Đổi dấu trọng số trên tất cả các cạnh thuộc đường đi đơn từ đỉnh ~u~ đến đỉnh ~v~ (giá trị trọng số ~w~ đổi dấu từ ~w \rightarrow -w~ và ngược lại từ ~-w \rightarrow w~);

• Sum ~u~ ~v~: Tính tổng trọng số các cạnh trên đường đi từ đỉnh ~u~ đến đỉnh ~v~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^4)~, là số lượng đỉnh của đồ thị;

• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~ ~(0 \le u_i, v_i < n, |w_i| \le 1000)~ là cạnh thứ ~i~ nối giữa đỉnh ~u_i~ và đỉnh ~v_i~ có trọng số ~w_i~.

• Dòng tiếp theo chứa số nguyên ~m~ ~(1 \le m \le 2 \cdot 10^4)~ là số thao tác thực hiện,

• ~m~ dòng tiếp theo, mỗi dòng chứa thao tác thuộc một trong ba dạng: C ~i~ ~x~; N ~u~ ~v~; Sum ~u~ ~v~.

Output

Ghi ra tổng trọng số tính được của thao tác Sum, mỗi kết quả ghi trên một dòng.

Scoring

Sample Input 1

3
0 1 1
1 2 -2
5
SUM 0 2
N 0 2
SUM 0 2
C 1 3
SUM 0 2

Sample Output 1

-1
1
5