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 speciﬁcation

For the purpose of this task, the road is an inﬁnite 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 diﬀerent
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 speciﬁcation

The ﬁrst line of the input ﬁle 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 ﬂoating-point number x
_{end}(0.5 ≤ x_{end}≤ 1500.0): the destination - a ﬂoating-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 ﬁrst one a
ﬂoating-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} ﬂoating-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
_{1}< ⋯ < 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 ﬁrst interval starts at 0 or later, the last interval ends at 10
^{6}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-speciﬁc 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 speciﬁcation

For each test case, output a single line with a ﬂoating-point number on it – the earliest time Peter can be
parked (v = 0) at position x_{end}. Output suﬃciently many decimal places. Answers with absolute or relative error
up to 10^{−6} will be accepted.

Example

input

1

10 1 3 0

10 1 30 1

5 1 2 3

10 1 3 0

10 1 30 1

5 1 2 3

output

6.32455532034

6.32882800594

6.32882800594

In the ﬁrst 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.