Description

You are now in an airport with $G$ boarding gates, numbered from $1$ to $G$. Gate $i$ is $100i$ meters away from the airport entrance.

There are also $N$ horizontal moving walkways in the airport. The $i$-th walkway moves one-way from gate $A_i$ to another gate $B_i$ at $S_i$ meters per minute. At any point in the corridor, in the same direction (toward the airport entrance or away from the airport entrance), there is at most one moving walkway in motion. However, it is possible that two moving walkways start from the same gate and have the same direction and the same destination.

You can walk along the corridor at speed $W$ meters per minute. When you are at the start of a moving walkway, you may choose to step onto it. If you do, it will take you to its endpoint. Even if a walkway passes through some position that is not its start or end, you cannot get on or off at that position. While you are on moving walkway $i$, your speed is $W+S_i$ meters per minute.

While waiting for your delayed flight, for fun you ask yourself $Q$ questions. The $i$-th question asks for the shortest time to get from gate $X$ to gate $Y$. To make it more interesting, you decide that if you answer any question incorrectly, you will not board the plane, so you had better not mess it up.

Input Format

The first line contains four integers $G, W, N, Q$, representing the number of gates, walking speed, the number of horizontal moving walkways, and the number of queries.

The next $N$ lines each contain three integers $A_i, B_i, S_i$, representing the start gate, end gate, and speed of moving walkway $i$. Here $A_i\ne B_i$.

The next $Q$ lines each contain two integers $X, Y$, representing the start gate and the destination gate.

Output Format

Output $Q$ lines. Each line contains one real number, the minimum number of minutes needed to go from gate $X$ to gate $Y$.

Your answer will be judged as follows: if $D$ is the standard answer, then any result in the range $[D\times (1-10^{-4}), D\times (1+10^{-4})]$ is considered correct.

6 10 3 4
2 3 15
4 2 150
3 6 290
3 2
2 3
1 4
4 6

10.0
4.0
24.0
6.25

Hint

For the first query, you only need to walk from gate $3$ to gate $2$. The distance between the two gates is $100$ meters, and your speed is $10$ meters per minute.

For the second query, you should take the moving walkway from gate $2$ to gate $3$. The distance is $100$ meters, and your speed is $25$ meters per minute.

For the third query, you should spend $10$ minutes walking to gate $2$, then spend $4$ minutes taking the moving walkway described in query $2$, and then spend $10$ minutes walking to gate $4$.

For the fourth query, you should spend $1.25$ minutes taking the moving walkway from gate $4$ to gate $2$, then spend $4$ minutes taking the moving walkway from gate $?$ to gate $2$, and finally spend $3$ minutes taking the plane from gate $1$ to gate $6$.

For some testdata, at least one of $G, N, Q$ is small. This information may be useful, or it may not be.

For $100\%$ of the testdata, $1\le A_i, B_i, X, Y\le G\le 10^9$, $1\le N, Q\le 10^5$.

Translated by ChatGPT 5