该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

给出N个区间，标号从1到N，区间范围的定义如下：

如果ti=1，那么区间i范围为[li,ri];

如果ti=2，那么区间i范围为[li,ri);

如果ti=3，那么区间i范围为(li,ri];

如果ti=4，那么区间i范围为(li,ri).

提示：

1）满足 a ≤ x ≤ b 的实数 x 的集合,表示为 [a,b],叫做闭区间；

2）满足 a ＜ x ＜b 的实数 x 的集合,表示为 ( a,b ),叫做开区间；

3）满足 a ≤ x ＜b,a ＜x ≤ b 的实数 x 的集合,分别表示为 [ a,b ),( a,b ],叫做半开区间。

求问有多少对整数对(i,j)满足1≤i＜j≤N，且区间i和区间j有交集？

输入格式

输入共N+1行

第一行包括一个整数N

接下来N行，每行包括3个整数：ti、li、ri。

输出格式

输出满足上述条件的整数对的个数。

样例

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,2]，区间2为[2,3)，区间3为(2,4]。一共有两对整数对满足上述条件：(1,2)和(2,3)。对于第一对，两个区间的交集为[2,2]；对于第二对，两个区间的交集为(2,3)。

2≤N≤2000

1≤ti≤4

1≤li<ri≤10^9

保证所有输入的值都是整数。