Discount Event

The country consists of $N$ cities and $N-1$ roads. The cities are numbered from $1$ to $N$, and the roads are numbered from $1$ to $N-1$. Road $i$ connects cities $A_i$ and $B_i$ in both directions, and traveling along it costs $W_i$. For any two cities, you can travel between them using one or more roads.

The distance between two cities is the minimum cost of getting from one city to the other by using one or more roads.

You are the president of a road company, and you plan a discount event for the holidays. There are $Q$ plans. In plan $i$, every road on the shortest path from city $X_i$ to city $Y_i$ is discounted so that its cost becomes 0. For each plan, output the maximum distance between two cities.

The first line contains the number of cities $N$. Each of the next $N-1$ lines contains three integers $A_i$, $B_i$, and $W_i$, separated by spaces. These are the two cities connected by road $i$ and the travel cost of that road.

The next line contains the number of plans $Q$. Each of the next $Q$ lines contains two integers $X_i$ and $Y_i$, separated by a space, which describe plan $i$.

Print $Q$ lines. The $i$-th line contains the answer for plan $i$.

• $2 \le N \le 100\,000$
• $1 \le A_i, B_i \le N$ ($1 \le i \le N-1$)
• $A_i \ne B_i$ ($1 \le i \le N-1$)
• $1 \le W_i \le 10^9$ ($1 \le i \le N-1$)
• The given country forms a valid tree.
• $1 \le Q \le 100\,000$
• $1 \le X_i, Y_i \le N$ ($1 \le i \le Q$)
• $X_i \ne Y_i$ ($1 \le i \le Q$)