Cạnh Lớn Nhất Trên Đường

Có $T$ bộ dữ liệu. Mỗi bộ là một cây $n$ đỉnh, các cạnh được đánh số $1,\dots ,n-1$ theo thứ tự nhập và có trọng số dương. Sau đó là một chuỗi lệnh:

• $QUERY$ $u$ $v$: in trọng số lớn nhất trong các cạnh trên đường từ $u$ đến $v$;
• $CHANGE$ $i$ $w$: đổi trọng số cạnh số $i$ thành $w$;
• DONE: kết thúc bộ dữ liệu.

Khi $u=v$, đường không có cạnh và kết quả là $0$.

Input

• Dòng đầu chứa $T$. Mỗi bộ bắt đầu bằng $n$, tiếp theo là $n-1$ dòng $u$ $v$ $w$, rồi các lệnh cho đến DONE.

Output

• In một dòng cho mỗi lệnh $QUERY$.

Constraints

• $1\le T\le 20,1\le n\le 10^4$.
• $1\le w\le 10^6$; mỗi bộ có không quá $2\cdot 10^4$ lệnh trước DONE.
• Các cạnh tạo thành một cây.

Scoring

• Subtask $1$ ($50\%$): $n$ và số lệnh không quá $50$. Subtask $2$: không giới hạn thêm.

Example

1
5
1 2 4
1 3 7
3 4 2
3 5 6
QUERY 2 4
CHANGE 2 1
QUERY 2 4
CHANGE 3 9
QUERY 4 5
QUERY 1 1
DONE

7
4
9
0