Description

This trip takes place in a country with $N$ cities and $(N-1)$ bidirectional roads, and it is guaranteed that any two cities are reachable from each other.

To beautify the environment, all roads are built along rivers. This means Xiao Xi can make a boat by himself and then row along a road, so each time he traverses an edge, he may either walk on land or go by boat on the river.

Of course, because of downstream and upstream effects, there is a parameter $z_i$. In other words, if the time to walk across this edge on land is $a_i$, then the time to row downstream is $a_i-z_i$ (guaranteed to be greater than $0$), and the time to row upstream is $a_i+z_i$. However, building a boat takes $L$ time, and once a person gets on land, they must abandon the boat.

Now Xiao Xi wants you to help compute the shortest time from $u$ to $v$.

Note: A boat can be used continuously for multiple water segments (as long as you do not get off the boat).

Input Format

The first line contains three integers $N,L,T$.

The next $(N-1)$ lines each contain five integers $x_i,y_i,a_i,z_i,type_i$, where $type_i=1$ means the water flows from $x_i$ to $y_i$, and $type_i=0$ means the water flows from $y_i$ to $x_i$.

The next $T$ lines each contain two integers $u_i,v_i$, representing the start and end of each planned trip.

Output Format

Output $T$ lines, each containing one number, the answer for each query.

3 2 2
1 2 2 1 0
1 3 3 2 1
2 3
1 2

4
2

4 1 1
1 2 100 99 1
2 3 100 99 0
3 4 100 99 1
1 4

104

Hint

Explanation of Sample 1

The graph looks like this:

For the first query, from $2$ to $3$, we can build a boat at node $2$, costing $2$ time, then go downstream from node $2$ to $1$, costing $2-1=1$, and then go downstream to $3$, costing $3-2=1$. So the total cost is $2+1+1=4$.

Constraints

For $10\%$ of the testdata, $N,T\leq10^3$.

For another $10\%$ of the testdata, the shape of the tree is random.

For another $20\%$ of the testdata, all $u$ are the same, or all $v$ are the same.

The last test point provides a chain.

For $100\%$ of the testdata, $N,T\leq2\times10^5$, and $0<a_i,L\leq10^5$.

Translated by ChatGPT 5