Có một cây (đồ thị liên thông vô hướng không có chu trình) gồm $N$ đỉ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 truy vấn sau đây.

• 1 u v: In ra chi phí của đường đi từ $u$ đến $v$.
• 2 u v k: In ra đỉnh thứ $k$ trong số các đỉnh trên đường đi từ $u$ đến $v$. $k$ không lớn hơn số lượng đỉnh trên đường đi từ $u$ đến $v$.

Dữ liệu vào

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

Trong $N-1$ dòng tiếp theo, mỗi dòng chứa hai đỉnh $u$ và $v$ được nối bởi cạnh thứ $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$).

Trong $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ố nguyên dương không lớn hơn $1{,}000{,}000$.

Dữ liệu ra

In ra kết quả của từng truy vấn theo thứ tự, mỗi kết quả trên một dòng.

Ví dụ

Đầu vào 1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
2
1 4 6
2 4 6 4

Đầu ra 1

5
3