Background

Translated from @wlzhouzhuan.

Problem Description

After her previous artwork received positive reviews, Bessie got a job designing a painting kit. She designs the painting by choosing $N\ (1\le N\le 10^5)$ axis-aligned rectangles on the plane, with no two sides being collinear. The boundaries of these rectangles define the boundaries of the regions to be colored.

As an avant-garde artist, Bessie thinks this painting should look like a Holstein cow. More specifically, each region formed by the rectangles is colored either black or white, no two adjacent regions have the same color, and the region outside all rectangles is colored white.

After choosing the rectangles, Bessie wants you to output, depending on the parameter $T$:

• If $T=1$, output the total number of regions.
• If $T=2$, output the number of white regions and the number of black regions, in this order.

Note: The time limit for this problem is 4s, which is twice the default 2s.

Input Format

The first line contains $N$ and $T$.

The next $N$ lines each contain $x_1,y_1,x_2,y_2$, representing a rectangle with bottom-left corner $(x_1,y_1)$ and top-right corner $(x_2,y_2)$.

The testdata guarantees that the $x_i$ form a permutation of $1\sim 2N$, and the $y_i$ do as well.

Output Format

If $T=1$, output one integer; otherwise output two integers separated by a space.

2 1
1 1 3 3
2 2 4 4 

4

5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7

4 5

Hint

[Sample Explanation #1]

There are $2$ white regions and $2$ black regions, for a total of $4$ regions. All rectangle boundaries are connected, so this input satisfies subtask 3.

[Sample Explanation #2]

The rectangle in the upper-right is not connected to the other rectangles, so this input does not satisfy subtask 4.

[Constraints]

• subtask 1: testdata $3\sim 4$ satisfies $N\le 10^3$.
• subtask 2: testdata $5\sim 7$ satisfies that no two rectangles intersect.
• subtask 3: testdata $8\sim 10$ satisfies $T=1$, and all rectangle boundaries are connected.
• subtask 4: testdata $11\sim 13$ satisfies $T=2$, and all rectangle boundaries are connected.
• subtask 5: testdata $14\sim 18$ satisfies $T=1$.
• subtask 6: testdata $19\sim 23$ satisfies $T=2$.

Translated by ChatGPT 5