Cạnh Nhẹ Nhất Và Nặng Nhất

Cho một cây gồm $N$ đỉnh, đánh số từ $1$ đến $N$. Mỗi cạnh có một trọng số nguyên dương. Với hai đỉnh khác nhau $u,v$, đường đi duy nhất giữa chúng chứa ít nhất một cạnh.

Hãy tìm trên đường đi đó:

• trọng số nhỏ nhất trong các cạnh;
• trọng số lớn nhất trong các cạnh.

Cần trả lời $K$ truy vấn độc lập.

Input

• Dòng đầu chứa số nguyên $N$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a,b,w$: cạnh nối $a$ với $b$ có trọng số $w$.
• Dòng tiếp theo chứa số nguyên $K$.
• $K$ dòng cuối, mỗi dòng chứa hai đỉnh khác nhau $u,v$.

Output

• Với mỗi truy vấn, in trên một dòng hai số nguyên: trọng số nhỏ nhất và trọng số lớn nhất trên đường đi từ $u$ tới $v$, theo thứ tự đó.

Constraints

• $2\le N\le 10^5$.
• $1\le K\le 10^5$.
• $1\le a,b,u,v\le N$.
• $a\ne b$ trên mỗi cạnh; $u\ne v$ trong mỗi truy vấn.
• $1\le w\le 10^6$.
• $N-1$ cạnh tạo thành một cây.
• Input chỉ chứa một test case.

Scoring

• Subtask $1$ ($50$ điểm): $N,K\le 2000$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

7
1 2 8
1 3 3
2 4 6
2 5 10
3 6 4
6 7 12
4
4 5
4 7
3 7
1 5

6 10
3 12
4 12
8 10