Квадрати
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Дано поле $$$m \times m$$$. $$$n$$$ клітинок з цього поля чорні, всі інші — білі. Для кожного цілого числа $$$t$$$ від $$$0$$$ до $$$k^2$$$ знайдіть кількість квадратів $$$k \times k$$$, де рівно $$$t$$$ клітин чорні.

Вхідні дані

Перший рядок містить три цілі числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$, $$$2 \leq k \leq 4$$$).

Кожен з наступних $$$n$$$ рядків містить по два цілі числа $$$x_i$$$ та $$$y_i$$$ ($$$1 \leq x_i, y_i \leq m$$$) — координати чорної точки.

Гарантується, що усі пари різні.

Вихідні дані

Для кожного цілого числа $$$t$$$ від $$$0$$$ до $$$k^2$$$ виведіть відповідь.

Система оцінки

Рішення, які працюватимуть правильно при $$$m \leq 10^3$$$, отримають принаймні $$$30$$$ балів.

Рішення, які працюватимуть правильно при $$$k=2$$$, отримають принаймні $$$33$$$ бали.

Рішення, які працюватимуть правильно при $$$k \leq 3$$$, отримають принаймні $$$66$$$ балів.

Приклад

Вхідні дані
4 5 3
1 5
2 4
4 2
3 4
Вихідні дані
1 3 3 2 0 0 0 0 0 0 

Пояснення