CF2225E.Covering Points with Circles

You are given an array $ p $ containing $ n $ points with integer coordinates. These points are uniformly distributed inside some rectangle whose sides are parallel to the coordinate axes.

You need to place several circles so that the following conditions hold:

• the radius of each circle is equal to $ r $ , and its center has integer coordinates;
• for every pair of circles, the area of their intersection is $ 0 $ (but the circles may touch);
• at least $ 89 $ % of all points lie inside some circle or on the boundary of some circle (in other words, the number of points lying inside the circles or on their boundaries is at least $ \frac{89n}{100} $ ).

The rectangle in which the points from array $ p $ are distributed is unknown to you, but in all tests except for the example it is guaranteed that the area of one circle of radius $ r $ does not exceed $ \frac{1}{10} $ of the area of this rectangle.

The first line contains two integers $ n $ and $ r $ ( $ 4 \le n \le 10^4 $ , $ 10^2 \le r \le 10^3 $ ).

The next $ n $ lines each contain two integers $ p_{x} $ and $ p_{y} $ ( $ -10^5 \le p_x, p_y \le 10^5 $ ).

There are $ 40 $ tests in this problem. For each test except the example from the statement, the following constraints hold:

• the number of points is $ 10^4 $ ;
• all points are generated as follows: first, some integer $ x $ from $ 300 $ to $ 10^5 $ is chosen; after that, $ n $ distinct integer points are chosen uniformly at random in the rectangle $ [-x, x] \times [-x, x] $ ;
• the area of a circle of radius $ r $ does not exceed $ \frac{1}{10} $ of the area of the rectangle $ [-x, x] \times [-x, x] $ ;
• there exists a set of circles satisfying the conditions of the problem.

Hacks are disabled in this problem.

In the first line, output one integer $ k $ ( $ 1 \le k \le n $ ) — the number of circles. In each of the next $ k $ lines, output two integers $ x $ and $ y $ — the coordinates of the center of the $ i $ -th circle. The coordinates of centers of the circles you output should not exceed $ 2 \cdot 10^5 $ by absolute value.

If there are multiple solutions, output any of them. You do not need to minimize the number of circles, but it should not exceed $ n $ .

One possible covering for the first sample is shown in the figure: