Description

In ancient times, there were $n$ tribes spread across the territory of the Giri Kingdom. After setting up a 2D Cartesian coordinate system, each tribe is represented by an axis-aligned rectangle. Some lands may belong to multiple tribes at the same time. As time goes by, tribes may merge. Specifically, if the intersection area of two tribes is strictly greater than zero, they merge into a new tribe. The shape of the new tribe is the smallest axis-aligned rectangle that contains both original tribes.

Millions of years later, the tribes finally reach a stable state (no two tribes can be merged anymore), but Giri has already grown old. He wants to know how many tribes remain in the end, and the position of each tribe. Can you help him finish this task?

Input Format

The first line contains an integer $n$, representing the number of tribes in ancient times.

The next $n$ lines each contain four integers $x_1, x_2, y_1, y_2$, representing the coordinates of a tribe.

Output Format

The first line outputs an integer $m$, representing the number of tribes remaining after reaching stability.

The next $m$ lines each contain four integers $x_1, x_2, y_1, y_2$, representing the coordinates of a tribe.

Please output them in increasing lexicographical order (compare $x_1$ first; if $x_1$ is equal, compare $x_2$, and so on).

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

2
1 6 2 9
7 8 1 4

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le x1 < x2 \le 10^6$, $0 \le y1 < y2 \le 10^6$.

Translated by ChatGPT 5