Background

Account suspension due to “carding” in the judge.

Problem Description

Mayor Mirko lives in a city with $n$ neighborhoods. These $n$ neighborhoods are connected by $n - 1$ two-way roads, and from any neighborhood you can reach any other neighborhood.

Mirko wants to upgrade some roads to ease traffic. For each road, we know the current driving speed $v_i$ on this road, the upgrade cost $c_i$, and the driving speed $s_i$ after upgrading.

There are $q$ unhappy citizens who come to see Mirko. Each of them has their own upgrade suggestion. The $i$-th citizen suggests: “We should invest $e_i$ euros to upgrade the roads on the route between neighborhoods $a_i$ and $b_i$.”

For each suggestion, Mirko is interested in the following: if his goal is to maximize the minimum driving speed between neighborhoods $a_i$ and $b_i$, then what is that minimum driving speed when he can spend at most $e_i$ euros on upgrading roads.

Mirko immediately realizes that this problem is not simple, so he hires you to help him.

Input Format

The first line contains an integer $n\ (2\le n\le 10^5)$, the total number of neighborhoods.

The next $n - 1$ lines each contain five integers $x_i,y_i,v_i,c_i,s_i\ (1\le x_i,y_i\le n,1\le v_i<s_i\le 10^9,1\le c_i\le 10^9)$, meaning there is a road between neighborhoods $x_i$ and $y_i$. The current driving speed on this road is $v_i$, the upgrade cost is $c_i$, and the driving speed after upgrading is $s_i$.

The next line contains an integer $q\ (1\le q\le 10^5)$, the total number of unhappy citizens.

The next $q$ lines each contain three integers $a_i,b_i,e_i\ (1\le a_i,b_i\le n,a_i\neq b_i,1\le e_i\le 10^{18})$, with the meaning as described above.

Output Format

Output $q$ lines, where each line is the answer for the corresponding citizen’s suggestion.

6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

7
5
11

4
1 2 5 5 8
2 3 4 6 9
3 4 6 10 7
4
1 4 16
2 4 16
1 4 10
3 4 10

6
7
5
7

Hint

Sample explanation $1$: The figure below shows the city and the neighborhoods. On each edge, the numbers are the current driving speed, the upgrade cost, and the driving speed after upgrading.

If we upgrade the roads between $1$ and $2$, and between $1$ and $3$, then the driving speeds from $2$ to $4$ will become $10,9,7$. The minimum is $7$.

If we upgrade the road between $4$ and $3$, then the driving speeds from $6$ to $4$ will become $5,15$. The minimum is $5$.

If we upgrade the road between $3$ and $5$, then the driving speed from $5$ to $3$ will become $11$.

Translated by ChatGPT 5