In one very large and very respectable company there is a cloakroom with a coat hanger. It is represented by _n_ hooks, positioned in a row. The hooks are numbered with positive integers from 1 to _n_ from the left to the right.
The company workers have a very complicated work schedule. At the beginning of a work day all the employees are not there and the coat hanger in the cloakroom is empty. At some moments of time the employees arrive and some of them leave.
When some employee arrives, he hangs his cloak on one of the available hooks. To be of as little discomfort to his colleagues as possible, the hook where the coat will hang, is chosen like this. First the employee chooses the longest segment among available hooks following in a row. If there are several of such segments, then he chooses the one closest to the right. After that the coat is hung on the hook located in the middle of this segment. If the segment has an even number of hooks, then among two central hooks we choose the one closest to the right.
When an employee leaves, he takes his coat. As all the company workers deeply respect each other, no one takes somebody else's coat.
From time to time the director of this respectable company gets bored and he sends his secretary to see how many coats hang on the coat hanger from the _i_\-th to the _j_\-th hook inclusive. And this whim is always to be fulfilled, otherwise the director gets angry and has a mental breakdown.
Not to spend too much time traversing from the director's office to the cloakroom and back again, the secretary asked you to write a program, emulating the company cloakroom's work.
## Input
The first line contains two integers _n_, _q_ (1 ≤ _n_ ≤ 109, 1 ≤ _q_ ≤ 105), which are the number of hooks on the hanger and the number of requests correspondingly. Then follow _q_ lines with requests, sorted according to time. The request of the type "0 _i_ _j_" (1 ≤ _i_ ≤ _j_ ≤ _n_) — is the director's request. The input data has at least one director's request. In all other cases the request contains a positive integer not exceeding 109 — an employee identificator. Each odd appearance of the identificator of an employee in the request list is his arrival. Each even one is his leaving. All employees have distinct identificators. When any employee arrives, there is always at least one free hook.
## Output
For each director's request in the input data print a single number on a single line — the number of coats hanging on the hooks from the _i_\-th one to the _j_\-th one inclusive.
[samples]
在一家非常庞大且备受尊敬的公司里，有一个衣帽间，其衣架由 #cf_span[n] 个挂钩组成，排成一行。这些挂钩从左到右用正整数 1 到 #cf_span[n] 编号。
公司员工的工作安排非常复杂。工作日开始时，所有员工都不在，衣帽间的衣架是空的。在某些时刻，员工会到达，也有一些员工离开。
当某位员工到达时，他会将外套挂在一个可用的挂钩上。为了尽量减少对同事的不便，他选择挂钩的方式如下：首先，他在所有连续可用的挂钩中选择最长的一段；如果有多个这样的最长段，则选择最靠右的那个。然后，外套挂在该段的中间挂钩上。如果该段包含偶数个挂钩，则在两个中间挂钩中选择最靠右的那个。
当一位员工离开时，他会取走自己的外套。由于公司所有员工彼此非常尊重，没有人会拿走别人的外套。
时不时地，这家受尊敬公司的主管会感到无聊，于是派秘书去查看从第 #cf_span[i] 个挂钩到第 #cf_span[j] 个挂钩（含两端）之间挂了多少件外套。这个要求必须立即满足，否则主管会生气并精神崩溃。
为了减少在主管办公室和衣帽间之间来回奔波的时间，秘书请你编写一个程序来模拟公司衣帽间的工作流程。
第一行包含两个整数 #cf_span[n], #cf_span[q]（#cf_span[1 ≤ n ≤ 10^9], #cf_span[1 ≤ q ≤ 10^5]），分别表示衣架上的挂钩数量和请求数量。接下来是 #cf_span[q] 行请求，按时间顺序排列。类型为 "#cf_span[0] #cf_span[i] #cf_span[j]"（#cf_span[1 ≤ i ≤ j ≤ n]）的请求是主管的查询。输入数据至少包含一个主管请求。其余情况下，请求包含一个不超过 #cf_span[10^9] 的正整数——员工的标识符。每个员工标识符在请求列表中第奇数次出现表示其到达，第偶数次出现表示其离开。所有员工的标识符互不相同。当任何员工到达时，总至少有一个空闲挂钩。
对于输入数据中的每个主管请求，请在单独一行输出一个数字——从第 #cf_span[i] 个挂钩到第 #cf_span[j] 个挂钩（含两端）之间悬挂的外套数量。
## Input
第一行包含两个整数 #cf_span[n], #cf_span[q]（#cf_span[1 ≤ n ≤ 10^9], #cf_span[1 ≤ q ≤ 10^5]），分别表示衣架上的挂钩数量和请求数量。接下来是 #cf_span[q] 行请求，按时间顺序排列。类型为 "#cf_span[0] #cf_span[i] #cf_span[j]"（#cf_span[1 ≤ i ≤ j ≤ n]）的请求是主管的查询。输入数据至少包含一个主管请求。其余情况下，请求包含一个不超过 #cf_span[10^9] 的正整数——员工的标识符。每个员工标识符在请求列表中第奇数次出现表示其到达，第偶数次出现表示其离开。所有员工的标识符互不相同。当任何员工到达时，总至少有一个空闲挂钩。
## Output
对于输入数据中的每个主管请求，请在单独一行输出一个数字——从第 #cf_span[i] 个挂钩到第 #cf_span[j] 个挂钩（含两端）之间悬挂的外套数量。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of hooks, numbered $ 1 $ to $ n $.
Let $ Q \in \mathbb{Z}^+ $ be the number of queries.
Let $ R = (r_1, r_2, \dots, r_Q) $ be the sequence of queries, where each $ r_k \in \mathbb{Z}^+ \cup \{0\} $.
- If $ r_k = 0 $, it is a **range query**: $ (0, i, j) $ with $ 1 \le i \le j \le n $, asking for the number of coats on hooks $ [i, j] $.
- If $ r_k > 0 $, it is an **employee event**:
- First occurrence of ID $ r_k $: **arrival** — assign coat to a hook according to the rule below.
- Second occurrence of ID $ r_k $: **departure** — remove coat from the hook previously assigned to $ r_k $.
Let $ A \subseteq \{1, \dots, n\} $ be the set of occupied hooks (dynamic).
Let $ \text{map}: \mathbb{Z}^+ \to \{1, \dots, n\} $ be a bijection mapping each employee ID to the hook where their coat is hung.
**Rules for hook assignment upon arrival of employee with ID $ e $:**
Let $ F \subseteq \{1, \dots, n\} $ be the set of free hooks: $ F = \{1, \dots, n\} \setminus A $.
Partition $ F $ into maximal contiguous segments (intervals).
Let $ S $ be the set of such segments: $ S = \{ [l_1, r_1], [l_2, r_2], \dots, [l_m, r_m] \} $, sorted left to right.
For each segment $ [l, r] $, define its **length** $ L = r - l + 1 $.
Find all segments with **maximum** $ L $. Among those, select the **rightmost** segment $ [l^*, r^*] $.
Within $ [l^*, r^*] $, choose the hook $ h $ as follows:
- Let $ \text{mid} = \left\lfloor \frac{l^* + r^*}{2} \right\rfloor $,
- If $ (r^* - l^* + 1) $ is even, choose $ h = \left\lceil \frac{l^* + r^*}{2} \right\rceil $,
- Else, $ h = \left\lfloor \frac{l^* + r^*}{2} \right\rfloor $.
Thus, in both cases:
$$ h = \left\lceil \frac{l^* + r^*}{2} \right\rceil $$
Assign $ \text{map}(e) = h $, and update $ A \leftarrow A \cup \{h\} $.
**Constraints**
1. $ 1 \le n \le 10^9 $
2. $ 1 \le Q \le 10^5 $
3. Each employee ID appears exactly twice (arrival and departure), or not at all.
4. On arrival, at least one hook is free.
5. Departure only occurs if the employee’s coat is currently hung.
6. All employee IDs are distinct.
**Objective**
For each query $ r_k = (0, i, j) $, output:
$$
\left| A \cap [i, j] \right|
$$
i.e., the number of occupied hooks in the interval $ [i, j] $.