E. Покрытие кругами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$p$$$, который содержит $$$n$$$ точек с целыми координатами. Эти точки равномерно распределены в некотором прямоугольнике, оси которого параллельны осям координат.

Необходимо расположить несколько кругов таким образом, чтобы выполнялись следующие условия:

  • радиус каждого круга равен $$$r$$$, а его центр расположен в точке с целыми координатами;
  • для каждой пары кругов площадь их пересечения равна $$$0$$$ (но круги могут касаться);
  • хотя бы $$$89$$$% всех точек находятся в каком-либо круге или на границе какого-либо круга (другими словами, количество точек, находящихся внутри и на границах кругов, не меньше $$$\frac{89n}{100}$$$).

Прямоугольник, в котором распределены точки из массива $$$p$$$, вам не известен, однако во всех тестах, кроме примера из условия, гарантируется, что площадь одного круга с радиусом $$$r$$$ не превышает $$$\frac{1}{10}$$$ от площади этого прямоугольника.

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

Первая строка содержит два целых числа $$$n$$$ и $$$r$$$ ($$$4 \le n \le 10^4$$$, $$$10^2 \le r \le 10^3$$$).

Следующие $$$n$$$ строк содержат по два целых числа $$$p_{x}$$$ и $$$p_{y}$$$ ($$$-10^5 \le p_x, p_y \le 10^5$$$).

В задаче $$$40$$$ тестов. Для каждого теста, кроме примера из условия, выполняются следующие ограничения:

  • количество точек равно $$$10^4$$$;
  • все точки сгенерированы следующим образом: сначала выбрано некоторое число $$$x$$$ от $$$300$$$ до $$$10^5$$$; после этого в прямоугольнике $$$[-x, x] \times [-x, x]$$$ случайным образом выбрано $$$n$$$ целочисленных точек без повторений;
  • площадь круга с радиусом $$$r$$$ не превышает $$$\frac{1}{10}$$$ от площади прямоугольника $$$[-x, x] \times [-x, x]$$$;
  • существует набор кругов, удовлетворяющий условию задачи.

В задаче запрещены взломы.

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

В первой строке выведите одно число $$$k$$$ ($$$1 \le k \le n$$$) — количество кругов. В каждой из следующих $$$k$$$ строк выведите по два целых числа $$$x$$$ и $$$y$$$ — координаты центра $$$i$$$-го круга. Координаты центров кругов не должны превосходить $$$2 \cdot 10^5$$$ по абсолютному значению.

Если существует несколько решений, можно вывести любое из них. Минимизировать количество кругов не требуется, но оно не должно превысить $$$n$$$.

Пример
Входные данные
4 100
0 0
0 100
100 0
100 100
Выходные данные
1
70 70
Примечание

Один из возможных вариантов покрытия для первого примера изображен на рисунке