题目描述

给定 $N$ 个区间，编号从 $1$ 到 $N$。其中第 $i$ 个区间由一个标识符 $t_i$ 及两个端点 $l_i$, $r_i$ 组成。

• 若 $t_i = 1$，则表示闭区间 $[l_i,r_i]$
• 若 $t_i = 2$，则表示左闭右开区间 $[l_i,r_i)$
• 若 $t_i = 3$，则表示左开右闭区间 $(l_i,r_i]$
• 若 $t_i = 4$，则表示开区间 $(l_i,r_i)$

请计算有多少对整数 $(i,j)$ 满足 $1\le i < j \le N$，使得区间 $i$ 和区间 $j$ 相交。

$[X,Y],[X,Y),(X,Y],(X,Y)$ 是什么？

• 闭区间 $[X,Y]$ 是由所有满足 $X\le x\le Y$ 的实数 $x$ 组成的区间。
• 半开区间 $[X,Y)$ 是由所有满足 $X\le x< Y$ 的实数 $x$ 组成的区间。
• 半开区间 $(X,Y]$ 是由所有满足 $X< x\le Y$ 的实数 $x$ 组成的区间。
• 开区间 $(X,Y)$ 是由所有满足 $X< x< Y$ 的实数 $x$ 组成的区间。

简单来说，方括号 $[]$ 表示包含端点，圆括号 $()$ 表示不包含端点。

输入格式

输入从标准输入中给出，格式如下：

$N$

$t_1$ $l_1$ $r_1$

$t_2$ $l_2$ $r_2$

$\vdots$

$t_N$ $l_N$ $r_N$

输出格式

输出区间 $i$ 和区间 $j$ 相交的整数对 $(i,j)$的数量。

样例

3
1 1 2
2 2 3
3 2 4

2

19
4 210068409 221208102
4 16698200 910945203
4 76268400 259148323
4 370943597 566244098
1 428897569 509621647
4 250946752 823720939
1 642505376 868415584
2 619091266 868230936
2 306543999 654038915
4 486033777 715789416
1 527225177 583184546
2 885292456 900938599
3 264004185 486613484
2 345310564 818091848
1 152544274 521564293
4 13819154 555218434
3 507364086 545932412
4 797872271 935850549
2 415488246 685203817

102

说明/提示

样例 1 解释

根据题目描述，区间 $1$ 是 $[1,2]$，区间 $2$ 是$[2,3)$，区间 $3$ 是 $(2,4]$。

有两对整数 $(i,j)$ 使得区间 $i$ 和区间 $j$ 相交：$(1,2)$ 和 $(2,3)$。对于第一对，交集是 $[2,2]$，对于第二对，交集是 $(2,3)$。

数据范围

• $2\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ t_i\ \leq\ 4$
• $1\ \leq\ l_i\ \lt\ r_i\ \leq\ 10^9$
• 所有输入值都是整数。