E

Bounded by Lines

You are asked to write a program to plot a set of lines. Since, the dimension of the screen is finite, you want to show a portion of the plot.

Lets say, you have some lines, and want to show the portion between x=0 and x=10. Lines are infinitely long, but you only need to consider the portion you are going to show. Find the area bounded by the lines within this region. An area bounded by line may be defined as the set of points, for which, there is at least one line above it, and at least one line below it.

The shaded area in the graph is the area bounded by lines within the region x=0 and x=10.

Input

Input starts with an integer T(1<= T<=10), the number of test cases. This is followed by T test cases, each starts with an integer N(2<=N<=100000), the number of lines to follow. Next N lines each contain 4 real numbers, x₁, y₁, x₂, y₂,(-10001 < x₁,y₁,x₂,y₂ < 10001) denoting a line between the points (x₁,y₁) and (x₂,y₂).

The description of lines is followed by two integers x_l and x_u (-10001 < x_l, x_u < 10001).

There will be a blank line before each test case.

Output

For each test case, output the area bounded by the lines, within the region [x_l,x_u]. You can assume that, the output will never exceed 10⁹. Output having difference by no more than 0.001 with the official output shall be considered as correct.

Sample Input	Sample Output
4 2 0 0 5 5 0 0 10 5 0 5 3 0 0 10 5 5 0 10 5 5 0 15 5 0 10 3 0 0 10 5 5 0 10 5 5 0 15 5 0 5 2 0 0 1 1 0 0 -1 1 -1 1	6.250000 31.250000 18.750000 2.000000

Problem Setter: Manzurur Rahman Khan, Special Thanks: Samee Zahur

The image corresponds to the second test case