Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек (огромная шахматная доска). Изначально пастбище пустое.
ФД добавит n коров на пастбище одну за одной. i-ая корова занимает ячейку (x[i]
, y[i]
), которая отличается от ячеек, занятых всеми другими коровами.
Говорят, что корове "комфортабельно", если соседями по горизонтали и вертикали она имеет ровно три других коровы. ФД хочет посчитать, скольким коровам комфортабельно на его пастбище. Для каждого i в интервале 1..n, выведите общее количество коров, которым комфортабельно после того, как i-ая корова добавлена на пастбище.
Первая строка содержит одно целое число n (1 ≤ n ≤ 10^5
). Каждая из последующих n строк содержит два целых числа, указывающих (x, y) (0 ≤ x, y ≤ 1000) - координаты ячейки коровы. Гарантируется, что все ячейки различны.
Выведите в i-ой строке общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.
После того, как добавлены первые 4 коровы, корове в ячейке (1, 1) стало комфортабельно.
После того, как добавлены первые 7 коров, корове в ячейке (2, 1) стало комфортабельно.
После того, как добавлены первые 8 коров, корове в ячейках (2, 1) и (2, 2) стало комфортабельно.