| Codeforces Round 364 (Div. 2) |
|---|
| Закончено |
У Васи есть изначально пустая квадратная шахматная доска размера 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
На рисунке ниже изображено состояние доски после выставления каждой из трёх ладей. Серым цветом отмечены клетки, находящиеся не под боем.
