Gates

Interview

Time limit2sMemory limit256 MB

Summary
Find the minimum travel time for each query pair of gates using walking and directed walkways.
Level

Medium4 of 10

Topics
Shortest path, Graph
Solved
No attempts yet

Problem

An airport hallway has G gates. The entrance to gate i is 100·i metres from the start.

There are N moving walkways. Walkway i runs one way from gate Ai to gate Bi at speed Si metres per minute. At any point, at most one walkway moves in each direction.

You walk at speed W metres per minute. You may board a walkway only at its start and ride to its end. On walkway i your speed is W+Si.

Answer Q queries: the minimum time to travel from gate Xi to gate Yi.

Input

The first line has G, W, N, and Q. The next N lines contain Ai, Bi, and Si. The next Q lines contain Xi and Yi.

Output

Print Q lines, each with the minimum travel time in minutes. Answers within a relative error of 10^{-4} are accepted.

Examples2

  1. Example 1

    Input
    6 10 3 4
2 3 15
4 2 150
3 6 290
3 2
2 3
1 4
4 6
    Expected output
    10.0
4.0
24.0
6.25

  2. Example 2

    Input
    3 5 0 2
1 2
2 3
    Expected output
    20.0
20.0