Small M's laboratory has many power strips. These power strips are numbered from $1$ to $N$ and are arranged in a row from left to right.

Every morning, these power strips are unused. When a student arrives at the laboratory, they plug their laptop into an unused power strip. The students in the laboratory are very curious, and they complete this process as follows: First, they find the longest interval of unused power strips. If there are multiple intervals of the same length, they choose the one furthest to the left. Then, they plug their power cord into the middle of that interval. If the interval length is even, they also choose the one furthest to the left. When a student leaves the laboratory, they unplug their power cord. It is guaranteed that when a student arrives at the laboratory, there is at least one empty power strip.

Now, you are given the arrival and departure events of the students, as well as some queries. For each query, you need to calculate how many power strips have been used in the interval $[L, R]$.

Input

The first line contains two integers $N$ and $Q$, representing the number of power strips and the number of queries. Then $Q$ lines follow. Each line starts with an integer $K$. If $K=0$, it is followed by two integers $L$ and $R$ ($1 \le L \le R \le N$), representing a query. Otherwise, it represents student $K$ ($K \le 10^9$) arriving or leaving. If student $K$ has appeared an odd number of times, they are arriving; if an even number of times, they are leaving. Each student's ID is unique.

Output

For each query, output a single integer representing how many power strips have been used in the interval $[L, R]$.

Examples

Input 1

7 10
1
2
3
0 1 2
0 4 7
0 2 5
20
0 6 6
99
0 4 6

Output 1

1
2
2
1
3

Constraints

For $30\%$ of the data, $N \le 10^5, Q \le 10^3$. For $100\%$ of the data, $N \le 10^9, Q \le 10^5$.