2014 Canadian Computing Competition, Stage 2

Day 2, Problem 3: Gates

You're in an airport hallway with G (1 ≤ G ≤ 10⁹) gates, numbered from 1 to G in order. The entrance to gate i is 100·i metres from the start of the hallway.

There are also N (0 ≤ N ≤ 10⁵) moving walkways. The i-th walkway runs from the entrance to gate A_i (1 ≤ A_i ≤ G) to the entrance to a different gate B_i (1 ≤ B_i ≤ G) at a speed of S_i (1 ≤ S_i ≤ 10⁹) metres per minute, in one direction only. At every point along the hallway, there is at most one walkway moving in each direction (towards the start of the hallway, or away from it). However, it is possible that one walkway starts at the same gate as another walkway, moving in the same direction, ends.

You can walk in either direction along the hallway at a speed of W (1 ≤ W ≤ 10⁹) metres per minute. Additionally, when at the start of a walkway, you may choose to get on it, in which case it'll carry you directly to its end - you may not get on or off in between these points. While on walkway i, you will move at a speed of W + S_i metres per minute.

To amuse yourself while waiting for your flight (which, of course, has been delayed), you've posed Q (1 ≤ Q ≤ 10⁵) queries to yourself. The i-th query involves finding the minimal time in which you can get from gate X_i (1 ≤ X_i ≤ G) to gate Y_i (1 ≤ Y_i ≤ G). To make things more interesting, you've decided that you won't board your flight unless you can correctly answer all of these queries - so you'd better not screw up!

Input

The first line contains four integers: G (1 ≤ G ≤ 10⁹), the number of gates; W (1 ≤ W ≤ 10⁹), the walking speed; N (1 ≤ N ≤ 10⁵), the number of moving walkways, and Q (1 ≤ Q ≤ 10⁵), the number of queries.

The next N lines each contain three integers dealing with walkway i (i = 1..N): A_i (1 ≤ A_i ≤ G), the starting gate; B_i (1 ≤ B_i ≤ G), the ending gate; S_i (1 ≤ S_i ≤ 10⁹), the speed. Note that A_i ≠ B_i for any i.

The next Q lines each contain two integers dealing with query i = 1..Q: X_i (1 ≤ X_i ≤ G), the starting gate; and Y_i (1 ≤ Y_i ≤ G), the ending gate.

You can assume that for some test cases, at least some of G, N, Q are small. This information may be helpful, or not.

Output

The output is Q lines, each line containing one real number which is the minimal amount of time required to travel from gate X_i to Y_i (in minutes), for i = 1..Q. The output will be judged to be correct if the outputted answer is within a factor of 10⁻⁴ of the correct solution: that is, if D is the correct answer, values in the range [D·(1 − 10⁻⁴), D·(1 + 10⁻⁴)] will be judged as correct.

Sample Input

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

Sample Output

10.0
4.0
24.0
6.25

Explanation

For the first query, you should simply walk from gate 3 to gate 2, covering 100 metres at a speed of 10 metres per minute.

For the second query, you should immediately get on the moving walkway going from gate 2 to gate 3, covering 100 metres at a speed of 10 + 15 = 25 metres per minute.

For the third query, you should walk to gate 2 (taking 10 minutes), then take the walkway as before (taking 4 minutes), and then walk to gate 4 (taking 10 minutes).

Finally, for the fourth query, you should take the walkway from gate 4 to gate 2 (taking 1.25 minutes), then the walkway from gate 2 to gate 3 (taking 4 minutes), and finally the walkway from gate 3 to gate 6 (taking 1 minute).

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 17, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)