Bessie’s Cow Painting

Bessie has landed a job designing a painting set after her previous works received rave reviews. In her new design, she chooses N (1 ≤ N ≤ 10⁵) axis‐parallel rectangles in the plane, no two of which share a common line. The boundaries of these rectangles define the borders of the colored regions in the painting.

Being an avant‐garde artist, Bessie decided the painting should look like a Holstein cow. More precisely, every region (formed by the rectangular boundaries) is painted either black or white such that no two adjacent regions share the same color, and the region outside all rectangles is white.

After choosing the rectangles, Bessie asks you to output the result according to a parameter T:

• If T = 1, output the total number of regions.
• If T = 2, output the number of white regions followed by the number of black regions (in that order).
</p>

Note: The time limit for this problem is 4 seconds (twice the default 2 seconds).

Planar Geometry Hint: It can be shown that if we let I be the number of proper intersections between edges of different rectangles (i.e. intersections that occur strictly in the interior of the segments) and C be the number of connected components formed by all rectangle boundaries (where two rectangles are connected if they intersect), then the total number of regions is given by

\(F = I + 1 + C\).

Furthermore, if we properly 2–color the regions (with the unbounded outer region colored white) then the numbers of white (W) and black (B) regions satisfy

\(W = \frac{F + (1-C)}{2}, \quad B = \frac{F - (1-C)}{2}\).

inputFormat

The first line contains two integers T and N. Each of the following N lines contains four integers x₁ y₁ x₂ y₂ describing a rectangle, where (x₁, y₁) is its bottom–left corner and (x₂, y₂) is its top–right corner. It is guaranteed that no two vertical (or horizontal) edges share the same x–coordinate (or y–coordinate).

outputFormat

If T=1, output a single integer representing the total number F of regions. If T=2, output two integers: the number of white regions followed by the number of black regions.

sample

1 1
1 1 4 4

2

</p>