Incomparable rectangle pairs

Time limit2sMemory limit512 MB

Summary

Count the pairs of rectangles where neither fits inside the other after translation or a 90-degree rotation.

Level: Medium5 of 10
Topics: Sorting, Geometry, Segment tree
Solved: No attempts yet

Problem

A rectangle is axis-parallel when its top and bottom sides are parallel to the x-axis and its left and right sides are parallel to the y-axis. From here on, rectangle always means an axis-parallel rectangle.

One rectangle is described by four integers $x_1, y_1, x_2, y_2$ , where $(x_1, y_1)$ is the bottom-left corner and $(x_2, y_2)$ is the top-right corner. This rectangle is called a $(x_2 - x_1) \times (y_2 - y_1)$ rectangle.

Two rectangles are incomparable when neither one fits inside the other, even though translation and $90^\circ$ rotation are allowed. If one fits inside the other, the two rectangles are comparable. Given a list of rectangles, count the pairs of incomparable rectangles.

Input

The first line contains the number of rectangles $n$ . ( $0 \le n \le 10000$ )

Each of the next $n$ lines describes one rectangle with four integers $x_1$ , $y_1$ , $x_2$ , $y_2$ separated by a single space. $(x_1, y_1)$ is the bottom-left corner and $(x_2, y_2)$ is the top-right corner. Every coordinate satisfies $0 \le x_1 \le 10000$ , $0 \le y_1 \le 10000$ , $0 \le x_2 \le 10000$ , $0 \le y_2 \le 10000$ .

Output

Print the number of pairs of incomparable rectangles on one line.

Examples2

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

Example 2

Input

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

Expected output