Barn Expansion

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 25000 non-overlapping axis-aligned rectangles, count how many touch no other rectangle at any corner or along any wall.

Level: Medium7 of 10
Topics: Geometry, Sorting, Implementation
Solved: No attempts yet

Problem

Farmer John has $N$ rectangular barns ( $1 \le N \le 25000$ ) on his farm. Every barn has sides parallel to the $x$ - and $y$ -axes, and its corner coordinates are integers between $0$ and $1{,}000{,}000$ . The barns do not overlap, although they may share corners and/or sides with one another.

Because he has more cows to milk this year, Farmer John wants to expand some of his barns. A barn has room to expand only if it does not share a corner or a wall with any other barn — that is, all four of its walls can be pushed outward by at least some small amount without bumping into another barn. If two barns meet at a single corner, neither of them can expand.

Determine how many barns have room to expand.

Input

Line 1: a single integer $N$ .
Lines 2 to $N+1$ : four space-separated integers $A$ , $B$ , $C$ , $D$ describing one barn. Its lower-left corner is at $(A, B)$ and its upper-right corner is at $(C, D)$ , with $0 \le A < C \le 1000000$ and $0 \le B < D \le 1000000$ .

Output

A single integer: the number of barns that have room to expand.

Hint

In the example, only the first two barns listed can expand. Each of the other three barns touches at least one other barn at a corner or along a wall, so none of them can expand.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
1
0 0 1000000 1000000
```
Expected output
```
1
```
Example 3
Input
```
2
0 0 2 2
2 0 4 2
```
Expected output
```
0
```
Example 4
Input
```
2
0 0 2 2
2 2 4 4
```
Expected output
```
0
```