403376: GYM101147 B Street

As everyone knows. The last ACM-ICPC was in Phuket, Thailand. One thing about Phuket is that it has a very hot weather. So walking in the sunlight is a harder task than you might think!

Joud was walking in one of the famous markets of the city. One street was full of flower shops. Joud hates flowers, so he decided to go through this street while walking the minimum distance possible in sunlight.

Fortunately, some of the shops have big umbrellas placed in front of them, forming rectangular shadow spots.

Given the positions of these spots. What's the minimum distance that Joud has to walk in the sunlight in order to get to the end of the street?

Note that the street is a rectangular shape and Joud can start from any point at the start line and wants to reach any point at the end line of the street.

The first line of the input will contain T the number of test cases.

Each test case starts with three integers on a single line (0 < N ≤ 100), the number of rectangular spots, (0 < L ≤ 10⁹), the length of the street, (0 < U ≤ 10⁹), the width of the street.

Then N lines follow, each describes a rectangular spot and contains four integers (0 < h ≤ 10⁹), the height of the spot ,(0 < w ≤ 10⁹), the width of the spot , (0 ≤ d ≤ 10⁹), the distance between the beginning of the street and the spot , (). If k is equal to 1 it means that the spot is sharing a side with the right side of the street, otherwise it's sharing a side with the left side of the street. It's guaranteed that there is no overlapping between spots, but they might touch. See the figure below.

For each test case print one number rounded to exactly 6 places after the decimal point. The solution to the problem above.

2
1 200 100
10 50 50 0
4 200 100
20 10 10 1
80 20 20 0
20 90 120 0
30 8 150 1

190.000000
70.198039

The next figure shows a possible solution for the second sample.