Shortest Time to Travel Through Airport Gates

You are at an airport which has \(G\) boarding gates numbered from 1 to \(G\). The distance from the airport entrance to gate \(i\) is \(100i\) meters.

There are also \(N\) unidirectional moving walkways. The \(i\)-th moving walkway goes from gate \(A_i\) to gate \(B_i\) with a speed of \(S_i\) meters per minute. When you are on walkway \(i\), your walking speed becomes \(W+S_i\) m/min. Note that you can only get on a walkway at its starting gate and can only get off at its ending gate. Moreover, at any point on the corridor there is at most one moving walkway moving in a given direction (either towards or away from the entrance), although there may be multiple walkways starting from the same gate with the same direction and destination.

You can also walk along the corridor at a speed of \(W\) m/min. The distance between any two gates \(i\) and \(j\) is \(100\times|i-j|\) meters, so walking from gate \(i\) to gate \(j\) takes \(\frac{100|i-j|}{W}\) minutes.

You are curious about \(Q\) queries. In the \(i\)-th query, you need to compute the minimum time required to travel from gate \(X\) to gate \(Y\). Be careful – a wrong answer might mean you miss your flight!

inputFormat

The first line contains four integers: \(G\) \(N\) \(W\) \(Q\) — the number of gates, the number of moving walkways, your walking speed (in m/min), and the number of queries.

Then \(N\) lines follow, each containing three integers \(A_i\), \(B_i\), and \(S_i\) describing a moving walkway from gate \(A_i\) to gate \(B_i\) with speed \(S_i\) m/min. The walking time on this walkway is \(\frac{100\times|B_i-A_i|}{W+S_i}\) minutes.

Then \(Q\) lines follow, each containing two integers \(X\) and \(Y\) representing a query (start gate and destination gate).

outputFormat

For each query, output the minimum time (in minutes) to travel from gate \(X\) to gate \(Y\). The answer should be printed on a separate line. It is recommended to output a floating-point number with at least 6 decimal places.

sample

5 2 10 2
1 3 5
3 5 2
1 5
1 4

30.000000
23.333333