У Васи есть изначально пустая квадратная шахматная доска размера n × n, и он последовательно выставляет на неё m ладей.
Клетка поля находится под боем ладьи, если существует хотя бы одна ладья, находящаяся в том же столбце или в той же строке, что и эта клетка. Если в клетке находится ладья, то она также находится под боем.
Вам известны позиции, в которые Вася будет выставлять ладей на доску. Перед вами стоит задача определить количество клеток, которые находятся не под боем, после каждой выставленной на доску ладьи.
Выходные данные
Выведите m чисел, i-е из которых равно количеству клеток, находящихся не под боем, после выставления на доску первых i ладей.
Примечание
На рисунке ниже изображено состояние доски после выставления каждой из трёх ладей. Серым цветом отмечены клетки, находящиеся не под боем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 1
3 1
2 2
|
4 2 0
|
|
2
|
5 2
1 5
5 1
|
16 9
|
|
3
|
100000 1
300 400
|
9999800001
|