P7359 "JZOI-1" Travel

New Year is coming soon. Xiao Xi wants to take a long trip, but he has not decided where to start or where to go.

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).

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 $T$ lines, each containing one number, the answer for each query.

### 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