SCUSA Region ICPC Masthead ACM Balloon Logo
2017 ACM ICPC South Central USA Regional Programming Contest

J - Ring String

Figure 1: A strand of disks along a wall
Figure 1: A strand of disks along a wall

Suppose you want to decorate a party room wall with a string of rings, each having one-foot diameter and each touching the next ring at precisely one point. You cannot necessarily string the rings in a straight line because there are rectangular pictures on the wall that you must avoid. From a given starting point against the left end of the wall you want to use as few rings as possible so that the last ring is less than one foot from the right end of the wall. Using the minimum number of rings, you also wish to minimize the distance between the final ring and the right wall.

Figure 1 shows such an optimal solution, with the minimum number of rings and with the distance to the right wall (shown as a red segment) minimal among those solutions with the fewest rings.

The pictures on the wall will have some characteristics upon which you may depend:


The first line of input C is an integer, the number of test cases, 1 ≤ C ≤ 100.

All distances are measured in feet. For each test case, the first line of input contains three integers, N, S, and W, where 1 ≤ N ≤ 6 is the number of pictures on the wall, 1 ≤ S ≤ 99 is the starting ring’s center height above the floor, and 1 ≤ W ≤ 99 is the width between the left and right walls. The center of the starting disk will be 0.5 feet from the left wall. The second line contains picture position information for the N pictures in order from the left side of the room to the right. Each picture is given by four integer distances in feet, L R B T. Here L and R are the distances from the left end of the wall to the left and right edges of the picture, and B and T are the distances from the floor to the bottom and top edges of the picture. For each picture L + 2 ≤ R and 2 ≤ B < T . For the leftmost picture, 2 ≤ L. For the rightmost picture, R ≤ W − 2. The R distance for one picture is always at least 2 less than the L distance for the next picture to the right.

Assume the ceiling of the room is at least two feet higher than the center of the initial ring and the tops of all the pictures, so it is out of the way, and its exact height is not relevant.


For each test case, output a single floating-point number: M + d, where M is the minimal number of rings in a string ending with rightmost point less than one foot from the right wall, and d is the minimal distance from the right wall to the rightmost point on the Mth ring. The number that you output should be accurate to within an absolute or relative error of 10-6.

Note that the form of the output is such that there is no special roundoff issue if you have a ring’s right point at a distance very close to one foot from the right wall: with a distance one or over, there is room for one more ring, and the remaining distance to the wall goes down by one to compensate.

Sample Input

2 10 12
4 6 8 16 8 10 2 9

Sample Output