Cho một cây gồm \(N\) nút đánh số từ \(1 \rightarrow N\). Các cạnh của cây đánh số từ \(1 \rightarrow 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\)

Dữ liệu vào

• Input là một bộ gồm nhiều test. Dòng đầu của input là số test \(t\) \((t \le 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 \le 10^4)\). \(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á \(10^7\)

Dữ liệu ra

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

Input 1

1

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

Output 1

1
3