D. Кай и вечность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Снежная королева, уходя, дала Каю задание выложить из льдинок слово «вечность». Кай очень серьёзно взялся за задание, поскольку если Кай сумеет это сделать, то он станет сам себе господин, и ему подарят весь мир и пару коньков.

Под дворцом Снежной королевы расположено бесконечное клеточное поле. На нём хаотично разбросаны n льдинок, причём каждая льдинка лежит в центре ячейки клеточного поля и никакие две льдинки не лежат в одной ячейке. Для оценки сложности задания Кай смотрит на некоторые квадраты размера k × k с углами, лежащими в узлах поля, и сторонами, параллельными осям координат, и считает количество льдинок внутри квадрата.

Однако так Кай смотрит только на сложность какого-то фрагмента поля. Для того чтобы правильно оценить сложность всего поля в целом, Кай придумал такой критерий: для каждого x (1 ≤ x ≤ n) он хочет узнать количество квадратов k × k с углами, лежащими в узлах поля, и сторонами, параллельными осям координат, в которых содержится ровно x льдинок.

Помогите Каю оценить сложность задания, полученного от Снежной королевы.

Входные данные

В первой строке вводятся числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 300) — количество льдинок и параметр k соответственно. В следующих n строках вводятся по два целых числа xi и yi ( - 109 ≤ xi, yi ≤ 109) — координаты ячеек, в которых лежат льдинки. Гарантируется, что никакие две льдинки не лежат в одной ячейке.

Выходные данные

Выведите n чисел: количество квадратов k × k, содержащих ровно 1, 2, ..., n льдинок соответственно.

Пример
Входные данные
5 3
4 5
4 6
5 5
5 6
7 7
Выходные данные
10 8 1 4 0