Description

Xiao FF’s last line of defense is a trench of length $n$. Xiao FF has infinitely many types of mines, and each time an SCV can lay mines of a single type on the interval $[L, R]$, with this type being different from any type used before. Since the situation is urgent, at some moments Xiao FF may ask how many different types of mines are currently in the interval $[L', R']$, and he wants you to answer as quickly as possible.

Input Format

The first line contains two integers $n$ and $m$, where $n$ is the length of the defense line and $m$ is the total number of SCV laying operations and Xiao FF’s queries.

Each of the next $m$ lines contains three integers $q, l, r$:

• If $q = 1$, the SCV lays mines of a single, previously unused type on the interval $[l, r]$.
• If $q = 2$, Xiao FF asks how many different types of mines are currently in the interval $[l, r]$.

Output Format

For each of Xiao FF’s queries, output one answer (one per line), which is the current number of mine types in the specified interval.

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

1
2

Hint

Constraints

• For $30\%$ of the testdata, $0 \le n, m \le 1000$.
• For $100\%$ of the testdata, $0 \le n, m \le 10^5$.

Translated by ChatGPT 5