Codeforces Round 359 (Div. 1) |
---|
Закончено |
Снежная королева, уходя, дала Каю задание выложить из льдинок слово «вечность». Кай очень серьёзно взялся за задание, поскольку если Кай сумеет это сделать, то он станет сам себе господин, и ему подарят весь мир и пару коньков.
Под дворцом Снежной королевы расположено бесконечное клеточное поле. На нём хаотично разбросаны 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
Название |
---|