Дан массив $$$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 1000 00 100100 0100 100
1 70 70
Один из возможных вариантов покрытия для первого примера изображен на рисунке
