Problem Statement

You are given N intervals numbered 1 through N, that are as follows:

• if t_i=1, Interval i is [l_i,r_i];
• if t_i=2, Interval i is [l_i,r_i);
• if t_i=3, Interval i is (l_i,r_i];
• if t_i=4, Interval i is (l_i,r_i).

How many pairs of integers $(i,j) satisfying 1 \leq i \lt j \leq N$ are there such that Interval i and Interval j intersect?
What are [X,Y],[X,Y),(X,Y],(X,Y)?

• A closed interval [X,Y] is an interval consisting of all real numbers x such that $X \leq x \leq Y$.
• A half-open interval [X,Y) is an interval consisting of all real numbers x such that $X \leq x < Y$.
• A half-open interval (X,Y] is an interval consisting of all real numbers x such that $X < x \leq Y$.
• A open interval (X,Y) is an interval consisting of all real numbers x such that X < x < Y.

Roughly speaking, square brackets [] mean the endpoint is included, and curly brackets () mean the endpoint is excluded.

Input

Input is given from Standard Input in the following format:
N
t_1 l_1 r_1
t_2 l_2 r_2
$\hspace{1cm}\vdots$
t_N l_N r_N

Output

Print the number of pairs of integers (i,j) such that Interval i and Interval j intersect.

Constraints

• $2 \leq N \leq 2000$
• $1 \leq t_i \leq 4$
• $1 \leq l_i \lt r_i \leq 10^9$
• All values in input are integers.

Sample Input 1

3
1 1 2
2 2 3
3 2 4

Sample Output 1

2

As defined in the Problem Statement, Interval 1 is [1,2], Interval 2 is [2,3), and Interval 3 is (2,4].
There are two pairs of integers (i,j) such that Interval i and Interval j intersect: (1,2) and (2,3). For the first pair, the intersection is [2,2], and for the second pair, the intersection is (2,3).

Sample Input 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

Sample Output 2

102

见题面 Input 部分

见题面 Output 部分