Problem E
Square Pie

You are working on an OCR (Optical Character Recognition) application to convert scanned images into text format. In addition to just being able to parse text, you plan to have your software recognize graphs and transcribe them in a meaningful way. Having already handled histograms, bar graphs, scatter plots and regular pie charts, you have now worked your way to square pie charts.

A square pie chart consists of a rectangle subdivided into regions by horizontal or vertical lines. Just like a regular pie chart, the different regions represents how large fractions of something (e.g., baked desserts) are taken up by various subcategories (e.g., pies, cookies, etc). See the figure below for an example.

Figure 1: A square pie chart. This is a drawing of the second example case.

The module you are working on will be given a set of horizontal and vertical line segments forming a square pie chart, and should compute the sizes of the different regions of the chart.

The set of line segments is guaranteed to have been constructed as described above. In other words, four of them form a rectangle constituting the boundary of the square pie chart, and then each remaining line segment divides one rectangle into two smaller ones. Note that this means that the line segments do not intersect, except that the endpoints of each line segment touches some other line segment. However, the order of the line segments in the input is completely arbitrary and you can not assume that they are given in the order they were drawn.

Input

The first line of input consists of a single integer $n$ ($4 \le n \le 100\, 000$), the number of lines of the pie chart. Each of the following $n$ lines consists of four integers $x_1$, $y_1$, $x_2$, $y_2$, indicating a line segment from $(x_1,y_1)$ to $(x_2,y_2)$. The line segment is either horizontal (i.e., $x_1 \ne x_2$ and $y_1 = y_2$) or vertical (i.e., $x_1 = x_2$ and $y_1 \ne y_2$). Each coordinate is at most $10^9$ in absolute value.

Warning

This problem has somewhat large amounts of input and output. We recommend you to make sure that your input and output are properly buffered in order to make the most of the few seconds of execution time that we give you.

Output

If there are $m$ regions in the pie chart, the output should consist of $m$ lines, giving the sizes of the different regions (as fractions of the entire chart), in non-increasing order. You do not need to worry about the precise formatting of the sizes (e.g., number of decimals), but the absolute error of each size must be smaller than $10^{-9}$.

4
2 2 6 2
6 2 6 6
6 6 2 6
2 6 2 2

1

8
6 2 0 2
0 0 6 0
0 2 0 0
2 2 2 1
3 1 3 0
0 1 6 1
6 0 6 2
2 1 2 0

0.333333333333
0.2500
0.1666666667
0.16666666667
0.0833333333