题目描述

小 M 的实验室有很多电源插排。这些插排的编号从 $1$ 到 $n$，由左向右排成一排。

每天早晨，这些插排都是没有被使用的。每当一个学生来到实验室，他就将自己的笔记本电源插到某一个未被使用的插排上。

实验室的同学们都很奇怪，他们完成这个过程是这样的：首先，他们找到还没有被使用的插排的最长区间。

如果有多个区间长度相同，他们就选择最靠右的那个。然后将自己的电源插到该区间的中间。

如果区间长度是偶数，他们同样选择靠右的那个。当一个同学离开实验室时,他会将自己的电源拔出来。

数据保证每一个同学来到实验室时，至少有一个空的插排。

需要计算在区间 $[l,r]$ 已经有多少个插排被使用了。

输入格式

第一行是两个整数 $n$ 和 $q$，表示插排数量和询问数量。

接下来 $q$ 行，每一行以一个整数 $k$ 开头。

如果 $k$ 为 $0$，接下来就是两个整数 $l$ 和 $r$，表示一个询问。

否则 $k$ 表示表示编号为 $k$ 的学生到来或离开。$k$ 的奇数次出现表示到来，偶数次出现表示离开。每个学生的编号都是唯一的。

输出格式

对于每一个询问，输出一个整数，表示询问区间内有多少个插排已经被使用。

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

1
2
2
1
3

提示

数据规模与约定

对于 $30\%$ 的数据，$n \le 10^5，q \le 10^3$；

对于 $100\%$ 的数据，$1\le n \le 10^9,1\le q \le 10^5,0\le k \le 10^9,1\le l\le r\le n$。