시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 512 MB106660.000%

문제

There are $n$ rectangles on the coordinate plane, with sides parallel to the coordinate axis. The $i$-th rectangle covers all points $(x, y)$ with $l_i \le x \le r_i$ and $d_i \le y \le u_i$.

For simplicity, for every $i \neq j$, we have $l_i \neq l_j$, $r_i \neq r_j$, $l_i \neq r_j$, $d_i \neq d_j$, $u_i \neq u_j$, $d_i \neq u_j$.

Count the number of triples $(i, j, k)$ with $1 \le i < j < k \le n$ for which $i$-th, $j$-th, and $k$-th rectangles are pairwise disjoint (every pair of them has no common points).

입력

The first line of the input contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), the number of rectangles.

The $i$-th of the next $n$ lines contains four integers describing the $i$-th rectangle: $l_i$, $r_i$, $d_i$, $u_i$ ($-10^9 \le l_i < r_i \le 10^9$,  $-10^9 \le d_i < u_i \le 10^9$).

It is guaranteed that, for every $i \neq j$, we have $l_i \neq l_j$, $r_i \neq r_j$, $l_i \neq r_j$, $d_i \neq d_j$, $u_i \neq u_j$, $d_i \neq u_j$.

출력

Output the number of triples $(i, j, k)$ with $1 \le i < j < k \le n$ for which $i$-th, $j$-th, and $k$-th rectangles are pairwise disjoint.

예제 입력 1

5
1 5 1 5
4 8 2 6
3 7 3 7
2 6 28 32
42 46 42 46

예제 출력 1

3

예제 입력 2

6
1 8 6 10
2 5 3 12
3 4 15 20
0 9 2 22
-5 22 -2 23
-7 11 -1 17

예제 출력 2

0