L. Tree Distance
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an unrooted weighted tree $$$T$$$ with vertices $$$1, 2, \ldots, n$$$. Please answer some queries.

We define $$$\texttt{dist}(i,j)$$$ as the distance between vertex $$$i$$$ and vertex $$$j$$$ in $$$T$$$.

For each query, you are given two integers $$$l, r$$$. Please answer the value of

$$$$$$\min_{l\le i \lt j\le r}(\texttt{dist}(i,j)).$$$$$$

Input

The first line contains one integer $$$n~(1\leq n\le 2 \times 10^5)$$$, the number of vertices in the tree.

Each of the next $$$n-1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by three integers $$$a_i, b_i, w_i$$$ $$$(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$$$, the labels of vertices it connects and its weight.

Then one line contains one integer $$$q~(1\leq q\le 10^6)$$$, the number of queries.

Each of the following $$$q$$$ lines contains two integers $$$l, r~(1\le l \le r\le n)$$$ describing a query.

It is guaranteed that the given edges form a tree.

Output

For each query, output the answer in one line. If there is no $$$i,j$$$ such that $$$1\le i \lt j\le r$$$, the answer is $$$-1$$$.

Example
Input
5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5
Output
-1
3
7
7
2