Giải bài trực tuyến

Cho một cây gồm N nút đánh số từ 1->N. Các cạnh của cây đánh số từ 1->N-1, mỗi cạnh có trọng số là một số nguyên. Bạn cần viết chương trình thực hiện dãy các lệnh sau:
CHANGE i v => Thay đổi trọng số của cạnh thứ i thành v
NEGATE a b => Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ a đến b
QUERY a b => Tìm trọng số lớn nhất của các cạnh nằm trên đường đi từ a đến b

Input

Input là một bộ gồm nhiều test. Dòng đầu của input là số test t ( t<=20 ). Tiếp sau đó là các test.
Mỗi test bắt đầu bằng một dòng trống. Dòng tiếp theo ghi một số N ( N<=10000 ). N-1 dòng tiếp theo, mỗi dòng ghi 3 số a, b và c mô tả một cạnh của cây nối a với b và có trọng số là c. Thứ tự của các cạnh chính là thứ tự xuất hiện trong input. Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá 50000). Cuối mỗi test ghi một từ "DONE".
Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá 10000000.

Output

Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu a = b thì ghi ra 0.

Example

Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3