Bobo is an expert in data structures! He wants to maintain a set $S$ of line segments. Initially, $S$ is empty. He will perform $q$ operations in sequence, where there are $2$ types of operations:

• Type $1$: Given $l, r$, insert the line segment $[l, r]$ into the set $S$.
• Type $2$: Given $l, r$, query the number of line segments $[x, y] \in S$ such that $x \leq l \leq r \leq y$.

Help Bobo find the answer for each query.

Input

The input file contains multiple test cases. Process until the end of the file.

The first line of each test case contains $2$ integers $n$ and $q$, where $n$ represents the maximum possible value of $r$ in the operations.

Each of the next $q$ lines contains $3$ integers $t_i, l_i, r_i$, representing that the $i$-th operation is of type $t_i$ with parameters $l_i$ and $r_i$.

Output

For each type $2$ query, output $1$ integer representing the corresponding count.

Examples

Input 1

1 2
1 1 1
2 1 1
4 4
1 1 4
2 2 3
1 1 4
2 2 3

Output 1

1
1
2

Constraints

• $1 \leq n, q \leq 10^5$
• $t_i \in \{1, 2\}$
• $1 \leq l_i \leq r_i \leq n$
• For operations where $t_i = 2$, the condition $r_i - l_i \leq 2$ holds.
• The number of test cases does not exceed $10$.