Квадрати

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

Input

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

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

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

Output

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

Examples

Note

Scoring

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

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

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