eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сусіди

Сусіди

Розглянемо прямокутник на декартовій площині з вершинами \textbf{(0, 0)} та \textbf{(w, h)}, де \textbf{w} та \textbf{h} - додатні цілі числа. Є \textbf{N} шпилів гір, розміщених у точках сітки на цьому прямокутнику. Точками сітки називаються точки з цілими координатами. Кожен хоче побудувати будинок, але правила такі: \begin{itemize} \item у кожній точці сітки може бути побудовано не більше одного будинку \item не можна будувати будинок на шпилях гір. \end{itemize} Тому є \textbf{(w+1)·(h+1)-N} можливих розміщень будників. Деякі з цих розміщень вважаються кращими за інші. Ми будемо казати, що точка сітки (\textbf{x}, \textbf{y}) має північного сусіда, якщо є шпиль у деякій точці \textbf{(x, y+d)}, де \textbf{d} - додатнє число. Аналогічно визначається південний, східний та західний сусіди. Таким чином, кожна точка сітки, яке не є шпилем, может мати від \textbf{0} до \textbf{4} сусідів. Чим більше сусідів, тим вважається кращим розміщення. Підрахуйте скільки точок сітки (не враховуючи шпилі) мають \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} сусіда. Напишіть програму, яка \begin{itemize} \item читає опис місцевості зі стандартного вводу \item обчислює кількість точок сітки, які мають \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} сусіда \item виводить результат у стандартний вивід. \end{itemize} \InputFile Перший рядок містить три цілих числа \textbf{w}, \textbf{h}, \textbf{N} (\textbf{1} ≤ \textbf{w}, \textbf{h} ≤ \textbf{10^9}), (\textbf{1} ≤ \textbf{N} ≤ \textbf{500000}), відокремлених пропусками. Наступні \textbf{N} рядків містять описи розміщень шпилів. Кожен з них описується двома цілими числами \textbf{x} та \textbf{y} (\textbf{0} ≤ \textbf{x} ≤ \textbf{w}), (\textbf{0} ≤ \textbf{y} ≤ \textbf{h}), відокремлених одним пропуском. Усв шпилі знаходяться у різних точках. \OutputFile Перший і єдиний рядок виводу містить \textbf{5} цілих чисел, відокремлених пропуском і позначають кількість точок решітки (виключаючи точки шпилів), які мають рівно \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} сусіди.
Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4 3 6
0 3
2 3
2 1
0 1
3 2
1 2
Вихідні дані #1
1 7 2 3 1

Пояснення: Двох сусідів мають точки (3,1) та (3,3), Трьох сусідів мають точки (1,1), (0,2), (1,3). Чотирьох сусідів має точка (2,2) Нуль сусідів має точка (4,0) а усі інші точки мають рівно по одному сусіду.