CF74D.Hanger

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.

一家规模庞大且声誉卓著的公司里设有一间衣帽间，内有一排衣帽架。该衣帽架由 n 个挂钩组成，从左至右依次用正整数 $1$ 到 $n$ 编号。

该公司员工的工作日程极为复杂。在每个工作日开始时，所有员工均未到岗，衣帽间内的衣帽架为空。在某些时刻，员工会陆续到达，也有些员工会离开。

当某位员工到达时，他会将外套挂在某个空闲的挂钩上。为尽可能减少对同事的干扰，他选择挂钩的方式如下：首先，在所有连续的空闲挂钩段中，选出长度最长的一段；若存在多个长度相同的最长段，则选择其中最靠右的一段；然后，将外套挂在该段正中间的挂钩上。若该段包含偶数个挂钩，则在两个中间挂钩中选择更靠右的那个。

当某位员工离开时，他会取走自己的外套。由于该公司所有员工彼此尊重，因此绝不会拿错他人的外套。

有时，这家声誉卓著公司的总经理会感到无聊，于是派秘书去查看从第 i 个挂钩到第 j 个挂钩（含端点）之间共挂有多少件外套。而这一任性要求必须立刻满足，否则总经理便会勃然大怒并精神崩溃。

为避免秘书在总经理办公室与衣帽间之间往返耗费过多时间，总经理请你编写一个程序，模拟该公司衣帽间的工作过程。

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.

第一行包含两个整数 $n$、$q$（$1 \leq n \leq 10^9$，$1 \leq q \leq 10^5$），分别表示衣架上的挂钩总数和请求总数。随后是按时间顺序排列的 $q$ 行请求。形如 “0 $i$ $j$”（$1 \leq i \leq j \leq n$）的请求为导演的请求。输入数据中至少包含一个导演的请求。其余所有请求均包含一个不超过 $10^9$ 的正整数——即员工标识符。在请求列表中，每个员工标识符的第奇数次出现表示该员工到达；第偶数次出现表示该员工离开。所有员工的标识符互不相同。每当有员工到达时，衣架上总存在至少一个空闲挂钩。

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.

对于输入数据中的每个主管请求，在单独一行上输出一个数字——即从第 $i$ 个到第 $j$ 个（含）挂钩上悬挂的大衣数量。