D. Вешалка
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

В одной очень большой и очень солидной компании в раздевалке есть вешалка для пальто. Она представляет собой n крючков, расположенных в ряд. Крючки пронумерованы натуральными числами от 1 до n слева направо.

В компании очень сложный распорядок работ у сотрудников. В начале рабочего дня все сотрудники находятся не на работе, а вешалка в раздевалке пуста. В некоторые моменты времени сотрудники приходят на работу, а в некоторые уходят.

Когда сотрудник приходит на работу, он вешает на один из свободных крючков свое пальто. Чтобы доставить своим коллегам как можно меньше неудобств, крючок, на который будет повешено пальто, выбирается следующим образом. Сначала выбирается самый длинный отрезок из подряд идущих пустых крючков. Если таких отрезков несколько, то выбирается самый правый из них. После этого пальто вешается на крючок, расположенный в середине этого отрезка. Если в отрезке четное количество крючков, то пальто вешается на правый из двух срединных крючков.

Когда сотрудник уходит с работы — он забирает свое пальто. Так как все сотрудники в компании очень уважают друг друга, никто не трогает чужие пальто.

Время от времени директору этой очень солидной компании становится скучно и он отправляет свою секретаршу посмотреть сколько пальто висят на вешалке с i-го по j-ый крючок включительно. И эту прихоть приходится всегда выполнять — иначе директор начинает злиться и у него случается нервный срыв.

Чтобы не тратить слишком много времени на перемещение от кабинета директора до раздевалки и обратно, секретарша попросила вас написать программу, эмулирующую работу раздевалки компании.

Входные данные

В первой строке содержатся два целых числа n, q (1 ≤ n ≤ 109, 1 ≤ q ≤ 105) — количество крючков на вешалке и количество запросов соответственно. Далее идет q строк с запросами, отсортированными по времени. Запрос вида «0 i j» (1 ≤ i ≤ j ≤ n) — запрос директора. Во входных данных имеется хотя бы один запрос директора. Во всех остальных случаях запрос содержит натуральное число, не превышающее 109 — идентификатор сотрудника. Каждое нечетное появление идентификатора сотрудника в списке запросов — это его приход на работу, каждое четное — его уход. Все сотрудники имеют различные идентификаторы. Во время любого прихода любого сотрудника всегда имеется хотя бы один свободный крючок.

Выходные данные

На каждый запрос директора в выходных данных выведите одно число на отдельной строке — количество пальто, висящих на крючках с i-го по j-ый включительно.

Примеры
Входные данные
9 11
1
2
0 5 8
1
1
3
0 3 8
9
0 6 9
6
0 1 9
Выходные данные
2
3
2
5