Giá Trị Cạnh

Cho một hệ thống gồm $N$ nút được kết nối với nhau tạo thành cấu trúc dạng cây, nghĩa là đồ thị vô hướng liên thông và không có chu trình. Các cạnh nối giữa các nút được đánh số thứ tự từ $1$ đến $N - 1$.

Bạn cần xử lý danh sách các yêu cầu thuộc một trong hai dạng sau:

• CHANGE i ti: Thay đổi trọng số của cạnh thứ $i$ thành $t_i$.
• QUERY a b: Tìm trọng số lớn nhất của cạnh nằm trên đường đi đơn từ nút $a$ đến nút $b$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 20$), đại diện cho số lượng bộ dữ liệu. Tiếp theo là $t$ bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa số nguyên $N$ ($1 ≤ N ≤ 10000$), đại diện cho số lượng nút.

Trong $N - 1$ dòng tiếp theo, dòng thứ $i$ mô tả cạnh thứ $i$ gồm ba số nguyên $a, b, c$ với $a, b$ ($1 ≤ a, b ≤ N$) và trọng số $c$ ($0 ≤ c ≤ 1000000$), thể hiện có một cạnh nối giữa nút $a$ và nút $b$.

Các dòng tiếp theo chứa các câu lệnh có dạng:

• CHANGE i ti với chỉ số cạnh $i$ ($1 ≤ i ≤ N - 1$) và trọng số mới $t_i$ ($0 ≤ t_i ≤ 1000000$): thay đổi trọng số của cạnh thứ $i$ thành $t_i$.
• QUERY a b với $a, b$ ($1 ≤ a, b ≤ N$): truy vấn trọng số lớn nhất trên đường đi giữa nút $a$ và nút $b$.

Mỗi bộ dữ liệu kết thúc bằng một dòng chứa từ khóa DONE.

Giữa hai bộ dữ liệu liên tiếp có đúng một dòng trống.

Kết quả

Với mỗi câu lệnh QUERY, in ra một số nguyên trên một dòng riêng biệt thể hiện kết quả tương ứng.

Chấm điểm

Subtask 1 (25 points). Cây có dạng đường thẳng hoặc dạng ngôi sao.

Subtask 2 (25 points). Không có thao tác CHANGE (tất cả câu lệnh đều là QUERY).

Subtask 3 (50 points). $1 ≤ t ≤ 20$; $1 ≤ N ≤ 10000$; $0 ≤ c ≤ 1000000$

Ví dụ

Input

1
4
1 2 5
2 3 10
3 4 3
QUERY 1 4
CHANGE 2 2
QUERY 1 4
QUERY 3 4
DONE

Output

10
5
3

Ghi chú

Giải thích ví dụ:

• Truy vấn QUERY 1 4 ban đầu đi qua các cạnh có trọng số $5, 10, 3$, giá trị lớn nhất là $10$.
• Lệnh CHANGE 2 2 cập nhật trọng số của cạnh thứ $2$ thành $2$.
• Truy vấn QUERY 1 4 tiếp theo đi qua các cạnh có trọng số $5, 2, 3$, giá trị lớn nhất là $5$.
• Truy vấn QUERY 3 4 đi qua cạnh thứ $3$ có trọng số $3$, giá trị lớn nhất là $3$.