Две карты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
twosegments.in
вывод
twosegments.out

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

Тибет расположен на прямой. У Доктора есть множество карт, на каждой из которых изображён некоторый отрезок этой прямой. Доктор Стрендж собирается взять с собой ровно две карты, при этом длина той области Тибета, которая изображена на этих картах, должна быть равна 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