Доктор Стрендж собирается в Тибет, чтобы найти замок Старейшины. Без карты ему не обойтись.
Тибет расположен на прямой. У Доктора есть множество карт, на каждой из которых изображён некоторый отрезок этой прямой. Доктор Стрендж собирается взять с собой ровно две карты, при этом длина той области Тибета, которая изображена на этих картах, должна быть равна s. Обратите внимание, что эта область не обязана быть связной, а если какая-то часть Тибета изображена на обеих картах, её нужно считать только один раз.
Прежде, чем отправиться в путешествие, Доктор приобретает новые карты и продаёт старые.
После каждого изменения коллекции карт он хочет узнать, сколько существует способов выбрать две карты, как описано выше.
В первой строке входного файла заданы целые числа s и n — длина, которая интересует Доктора, и количество изменений коллекции карт (1 ≤ s ≤ 109, 1 ≤ n ≤ 105).
В следующих n строках описаны события, происходящие с коллекцией карт:
Все координаты — целые числа, по модулю не превосходящие 5·108. Карты могут быть одинаковыми. Изначально в коллекции Доктора карт нет.
Для каждого события выведите количество способов выбрать две карты так, чтобы длина области Тибета, которая изображена на них, была равна s.
10 6
1 0 8
1 7 10
1 5 15
2 2
1 12 14
2 5
0
1
2
0
2
0