시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB98715973.750%

문제

A rectangle is axis-parallel if its top and bottom sides are parallel to the x-axis and its left and right sides are parallel to the y-axis. From now on by a rectangle we mean an axis-parallel rectangle.

A rectangle will be specified by a 4-tuple (x1, y1, x2, y2) in which (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. We will also say the rectangle (x1, y1, x2, y2) is a (x2 − x1) × (y2 − y1) rectangle.

Two rectangles are incomparable if neither will fit inside the other possibly with translation and 90 rotation; otherwise, the two rectangles are comparable. Given a list of rectangles, you are to output the number of pairs of incomparable rectangles.

입력

The first input line contains an integer which is the number of rectangles n (where 0 ≤ n ≤ 10000). Each of the next n lines describes a rectangle and contains four integers x1, y1, x2, y2, a space separates two adjacent integers. Recall that coordinates (x1, y1), (x2, y2) specify respectively the bottom-left and top-right corner of the rectangle. All coordinate values are in the range of 0 to 10,000; that is, 0 ≤ x1 ≤ 10000, 0 ≤ y1 ≤ 10000, 0 ≤ x2 ≤ 10000, 0 ≤ y2 ≤ 10000.

출력

The output file contains a single integer which is the number of pairs of incomparable rectangles.

예제 입력 1

3
0 0 2 2
0 0 3 1
1 1 3 4

예제 출력 1

1

Consider three rectangles:

  • the 2 × 2 rectangle A : (0, 0, 2, 2);
  • the 3 × 1 rectangle B : (0, 0, 3, 1);
  • the 2 × 3 rectangle C : (1, 1, 3, 4).

Rectangle pair AB is incomparable (neither can fit inside the other). But rectangle pair AC is comparable (A fits inside C after a translation), so is rectangle pair BC (B fits inside C after a 90 rotation and a translation).

예제 입력 2

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

예제 출력 2

4

Consider four rectangles:

  • the 1 × 3 rectangle A : (3,3,4,6);
  • the 3 × 1 rectangle B : (1,2,4,3);
  • the 2 × 2 rectangle C : (5,6,7,8);
  • the 2 × 2 rectangle D : (10,10,12,12).

There are four incomparable rectangle pairs AC, AD, BC, BD. Thus the answer is 4.