Internet Problem Solving Contest

• Easy input data set – M1
• Hard input data set – M2

Peter was supposed to catch a morning train at 7:30. But as usual, he overslept the alarm set to 6:30 and he just woke up with 7:29 on the clock. He only managed a single “Oh crap!” before the train was gone. Luckily for Peter, everything can still be saved. He can take his old car out of the garage and drive it to his destination.

Peter lives in the middle of an abandoned countryside. There is a single long straight road going across the countryside. Peter’s home and his destination both lie on this road.

Still, Peter has a valid reason to prefer the train. The whole countryside is covered by train tracks, and thus the road is riddled with railroad crossings. And as trains have priority over cars, you could easily end up waiting for a long time at some of those crossings.

Moreover, even if you are not waiting for a train to pass, you still need to approach the railroad crossings carefully – they are in pretty bad shape and if Peter were to drive carelessly, the crossing could easily break his old car.

Problem specification

For the purpose of this task, the road is an infinite straight line. Peter’s home, his destination, each of the railroad crossings, and Peter’s car should all be considered points. Peter’s car is the only point that will be moving, all the other ones are stationary. The movement of Peter’s car is continuous (not discrete).

We will be using a linear coordinate system on the road, with Peter’s home being at 0 and his destination at some x_end > 0. All coordinates are in meters, all speeds are in meters per second, all accelerations are in meters per second squared.

All the railroad crossings lie strictly between Peter’s home and his destination, at pairwise different coordinates x_i. In the input, their descriptions are ordered by their coordinate.

There are no other cars on the road. Peter’s car can move freely along the line, including the parts that are not between his home and his destination. However, the movement of his car is subject to the following constraints:

• The car’s acceleration (change of velocity over time) has to be between −a_max and a_max, inclusive. (E.g., if your current speed is v = 20 and a_max = 1.2, after 0.5 seconds your speed can be anything between 19.4 and 20.6, inclusive.)
• The car cannot enter a crossing when the crossing is closed because of a passing train.
• In general, the speed of the car has no upper bound – it can go arbitrarily fast.

  However, the railroad crossings are special: The maximum allowed speed at a railroad crossing is v_max (an integer).

  But even when driving slower than v_max, the bumping while crossing the railroad sometimes tends to resonate parts of Peter’s car and Peter fears that the car might break. He has already tested that this does not happen if the speed of his car is an integer less than or equal to v_max. He now refuses to drive over a railroad crossing using any other speed.

  Therefore, whenever the car crosses a railroad, its speed at that moment has to be a positive integer.

  (Note that zero is not allowed. Stopping at a railroad crossing is forbidden by law.)

Peter’s car starts stationary (v = 0) at his home. Calculate the shortest time in which it is possible to park the car (i.e., have v = 0 again) at Peter’s destination (x_end).

Input specification

The first line of the input file contains an integer t ≤ 500 specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a single line containing four numbers:

• a floating-point number x_end (0.5 ≤ x_end ≤ 1500.0): the destination
• a floating-point number a_max (0.1 ≤ a_max ≤ 10.0): the maximum acceleration
• an integer v_max (1 ≤ v_max ≤ 40): the maximum speed over a crossing
• an integer n: the number of railroad crossings (constraints are given below)

Next n lines describe railroad crossings, one per line. Each line starts with two numbers. The first one a floating-point number x_i: the coordinate of this crossing. The second one is a nonnegative integer m_i: the number of trains that will be passing through the crossing. Then, 2m_i floating-point numbers follow: for each train the start s_i,j and the end e_i,j of the time interval when the crossing is blocked by the train.

You may assume the following things about the crossings:

• Their coordinates are in sorted order: 0 < x₁ < ⋯ < x_n < x_end.
• The intervals when the crossing is blocked are given in chronological order, they do not overlap, and they do not even touch (i.e., the end of one interval is always strictly less than the start of the next one). The first interval starts at 0 or later, the last interval ends at 10⁶ or sooner.
• Assume that the intervals are open – if you arrive precisely at their start or end, you are still able to cross in either direction.

There should be no numerically unstable test cases in the test data. More precisely, for each test case we used: 1) if we make small changes to the values s_i,j and e_i,j, the optimal path remains essentially the same; and 2) if we make a small change to a_max, the optimal path remains essentially the same.

Subproblem-specific constraints

In the easy subproblem M1, 0 ≤ n ≤ 1 (i.e., there is at most one crossing) and 0 ≤ m_i ≤ 2 (there are at most two trains per crossing). In the hard subproblem M2, 0 ≤ n ≤ 30 and 0 ≤ m_i ≤ 25.

Output specification

For each test case, output a single line with a floating-point number on it – the earliest time Peter can be parked (v = 0) at position x_end. Output sufficiently many decimal places. Answers with absolute or relative error up to 10⁻⁶ will be accepted.

Example

In the first case, there is no crossing and so Peter may drive directly to his destination. The optimal strategy is to accelerate until he reaches x = 5, and then to brake for the rest of the way. Note that his maximum speed during this trip will exceed v_max.

In the second case the train will leave the crossing before Peter can possibly reach it. Still, the crossing limits the car speed. In the optimal solution Peter will cross the railroad crossing having speed v = 3.