You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

大地被雷暴一怒之下形成了 $n$ 个矩形。

题目描述

有 $n$ 个矩形，第 $i$ 个矩形的左上角为 $(ax_i,ay_i)$，右下角为 $(bx_i,by_i)$。

为了方便，我们保证 $ax_i,bx_i$ 和 $ay_i,by_i$ 它们内部分别互不相同。

现在求有多少三元组 $(i,j,k)$ 满足，第 $i$ 个矩形、第 $j$ 个矩形，第 $k$ 个矩形，它们之间两两不交。

输入格式

第一行，一个正整数 $n$ 表示矩形个数。

接下来 $n$ 行，每行 $4$ 个正整数，分别表示 $x_{1_i},x_{2_i},y_{1_i},y_{2_i}$。

输出格式

一行一个非负整数，表示三元组个数。

样例 #1

样例输入 #1

6
2 12 11 12 
10 11 1 7 
4 5 5 8 
6 13 3 15 
1 3 9 10 
9 15 6 13

样例输出 #1

6

样例 #2

样例输入 #2

见下发文件 rectangle2.in。

rectangle2.in

样例输出 #2

见下发文件 rectangle2.ans。

rectangle2.ans

样例 #3

样例输入 #3

见下发文件 rectangle3.in。

rectangle3.in

样例输出 #3

见下发文件 rectangle3.ans。

rectangle3.ans

样例 #4

样例输入 #4

见下发文件 rectangle4.in。

rectangle4.in

样例输出 #4

见下发文件 rectangle4.ans。

rectangle4.ans

样例 #5

样例输入 #5

见下发文件 rectangle5.in。

rectangle5.in

样例输出 #5

见下发文件 rectangle5.ans。

rectangle5.ans

提示

【样例 1 解释】

$6$ 种合法方案：

1. 1,2,3；
2. 1,2,5；
3. 1,3,5；
4. 2,3,5；
5. 3,4,5；
6. 3,5,6。

【数据范围】

对于所有数据保证：$n\le 2\times 10^5$，$1\le x_{1_i}<x_{2_i}\le 10^9$，$1\le y_{1_i}<y_{2_i}\le 10^9$。

保证 $x_{1_i},x_{2_i}$ 两两不同，$y_{1_i},y_{2_i}$ 两两不同。