$N$ đỉnh tạo thành một cây (đồ thị liên thông, vô hướng, không có chu trình). Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$.

Hãy viết chương trình thực hiện hai loại truy vấn sau:

• 1 i c: Thay đổi chi phí của cạnh thứ $i$ thành $c$.
• 2 u v: In ra chi phí lớn nhất trong số các cạnh trên đường đi đơn từ $u$ đến $v$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$).

$N-1$ dòng tiếp theo, dòng thứ $i$ chứa hai đỉnh $u$, $v$ mà cạnh thứ $i$ nối và chi phí $w$ của cạnh đó.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Chi phí của các cạnh luôn là số tự nhiên không lớn hơn $1{,}000{,}000$.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra kết quả trên một dòng, theo đúng thứ tự.

Ví dụ

Dữ liệu vào

3
1 2 1
2 3 2
3
2 1 2
1 1 3
2 1 2

Dữ liệu ra

1
3