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.

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.

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.