B. Клетки не под боем
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть изначально пустая квадратная шахматная доска размера n × n, и он последовательно выставляет на неё m ладей.

Клетка поля находится под боем ладьи, если существует хотя бы одна ладья, находящаяся в том же столбце или в той же строке, что и эта клетка. Если в клетке находится ладья, то она также находится под боем.

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

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

В первой строке входных данных находятся два числа n и m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n2)) — размер доски и количество ладей, которые будут выставлены на доску.

В следующих m строках следует по два целых числа xi и yi (1 ≤ xi, yi ≤ n) — номер строки и номер столбца клетки поля, в которую будет выставлена i-я ладья. Ладьи будут выставлять на доску в порядке следования во входных данных. Гарантируется, что в любую клетку поля будет выставлено не более одной ладьи.

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

Выведите m чисел, i-е из которых равно количеству клеток, находящихся не под боем, после выставления на доску первых i ладей.

Примеры
Входные данные
3 3
1 1
3 1
2 2
Выходные данные
4 2 0 
Входные данные
5 2
1 5
5 1
Выходные данные
16 9 
Входные данные
100000 1
300 400
Выходные данные
9999800001 
Примечание

На рисунке ниже изображено состояние доски после выставления каждой из трёх ладей. Серым цветом отмечены клетки, находящиеся не под боем.