Квадрати#76

Квадрати

2 секунды
256 мегабайт
Hard

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

Input

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

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

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

Output

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

Examples

Example 1

Loading
Loading

Note

Scoring

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

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

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