28971번 - Две карты 다국어

Доктор Стрендж собирается в Тибет, чтобы найти замок Старейшины. Без карты ему не обойтись.

Тибет расположен на прямой. У Доктора есть множество карт, на каждой из которых изображён некоторый отрезок этой прямой. Доктор Стрендж собирается взять с собой ровно две карты, при этом длина той области Тибета, которая изображена на этих картах, должна быть равна $s$. Обратите внимание, что эта область не обязана быть связной, а если какая-то часть Тибета изображена на обеих картах, её нужно считать только один раз.

Прежде, чем отправиться в путешествие, Доктор приобретает новые карты и продаёт старые.

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

В первой строке входного файла заданы целые числа $s$ и $n$ --- длина, которая интересует Доктора, и количество изменений коллекции карт ($1\le s\le 10^9$, $1\le n \le 10^5$).

В следующих $n$ строках описаны события, происходящие с коллекцией карт:

• Строка вида $1$ $l_i$ $r_i$ означает, что Доктор приобрёл новую карту, на которой изображена область Тибета от $l_i$ до $r_i$ ($l_i<r_i$).
• Строка вида $2$ $k$ означает, что Доктор продал карту, которая описывается в событии номер $k$. События нумеруются с единицы. Гарантируется, что событие номер $k$ --- это событие типа $1$. Ни одна карта не может быть продана больше одного раза.

Все координаты --- целые числа, по модулю не превосходящие $5\cdot10^8$. Карты могут быть одинаковыми. Изначально в коллекции Доктора карт нет.

Для каждого события выведите количество способов выбрать две карты так, чтобы длина области Тибета, которая изображена на них, была равна $s$.