题目描述

给定 $N$ 个区间，编号从 $1$ 到 $N$，每个区间的形式如下：

• 如果 $t_i=1$，则区间 $i$ 为闭区间 \[l_i,r_i\]；
• 如果 $t_i=2$，则区间 $i$ 为半开区间 $\[l_i,r_i)$；
• 如果 $t_i=3$，则区间 $i$ 为半开区间 (l_i,r_i\]；
• 如果 $t_i=4$，则区间 $i$ 为开区间 $(l_i,r_i)$。

有多少对整数 $(i,j)$ 满足条件 $1 \leq i \lt j \leq N$，使得区间 $i$ 和区间 $j$ 相交？

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

• 闭区间 \[X,Y\] 是包含所有满足 $X \leq x \leq Y$ 的实数 $x$ 的区间。
• 半开区间 $\[X,Y)$ 是包含所有满足 $X \leq x < Y$ 的实数 $x$ 的区间。
• 半开区间 (X,Y\] 是包含所有满足 $X < x \leq Y$ 的实数 $x$ 的区间。
• 开区间 $(X,Y)$ 是包含所有满足 $X < x < Y$ 的实数 $x$ 的区间。

大致地说，中括号 \[\] 表示端点包含在内，圆括号 $()$ 表示端点不包含在内。

约束条件

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

输入

从标准输入读入数据，输入格式如下：

$N$ $t_1$ $l_1$ $r_1$ $t_2$ $l_2$ $r_2$ $\hspace{1cm}\vdots$ $t_N$ $l_N$ $r_N$

输出

打印满足条件的整数对 $(i,j)$ 的数量，使得区间 $i$ 和区间 $j$ 相交。

示例输入1

3
1 1 2
2 2 3
3 2 4

示例输出1

2

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

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

示例输入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

示例输出2

102