Description

We have drawn $n$ rectangles on a plane. Each rectangle has its sides parallel to the coordinate axes, and all vertex coordinates are integers. We define a shape that satisfies the following properties to be a block:

1. Each rectangle is a block.

2. If two blocks have a segment of overlap, then these two blocks form a new block; otherwise, the two blocks are different.

Example:

In Figure $1$, the rectangles form two different blocks. In Figure $2$, the rectangles form one block.

Task:

Please write a program to:

1. Read the vertex coordinates of each rectangle from standard input.
2. Find the number of different blocks among these rectangles.
3. Output the result to standard output.

Input Format

The first line contains an integer $n$, where $1\le n\le 7000$, the number of rectangles. Each of the next $n$ lines gives the vertex coordinates of a rectangle. Each rectangle is described by four integers: the $x$-coordinate of the lower-left corner, the $y$-coordinate of the lower-left corner, the $x$-coordinate of the upper-right corner, and the $y$-coordinate of the upper-right corner. All coordinates are non-negative integers not greater than $10000$.

Output Format

Output a single integer — the number of different blocks formed by these rectangles.

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

2

Hint

Image link

The thick orange segments indicate where overlaps occur. The number in the center of each square denotes the ID of the block it belongs to.

Note: Corner touching does not count as the same block.

Translated by ChatGPT 5