Problem A
Closest Pair of Points in the Plane, but Nicer

Given a set $P$ of points in the plane, find a closest pair, i.e., a pair of points that minimises the Euclidean distance over all pairs of points in $P$.

Constraints and Subtasks

The number $n$ of points in $P$, always satisfies $2\leq n \leq 100\, 000$.

The problem is subdivided into simpler subtasks:

In subtask $1$, the points are on a line and if suffices to consider the $x$-coordinate. Subtask $2$ is small enough to be solved by the naïve approach that considers all pairs on points in quadratic time. You need this routine anyway for the base case in the intended divide-and-conquer solution, so it makes sense to solve this case first. In subtask $3$, because the points are uniformly distributed, there will not be too many points close to the separating line, so a much simpler “combine”-step than in the full solution should work. Subtask $4$ is merely a smaller version of the full problem that is more lenient towards non-optimised implementations of the indended solution.

Input

Input begins with the number $n$ of points in $P$. Then follows a list of $n$ points, one per line, each of the form $x$ $y$ with a single separating space. Coordinates are given as floating point values with at most $2$ decimals and absolute value bounded by $100\, 000$. Note that points need not be unique.

Output

Output a closest pair in $P$ on exactly two lines, each containing a point. The order of the points doesn’t matter; if there is more than one solution, any will do.

2
1.12 0
0 0.51

0.0 0.51
1.12 0.00

3
158 12
123 15
1859 -1489

123 15
158 12.00

3
21.12 -884.2
18.18 43.34
21.12 -884.2

21.12 -884.20
21.12 -884.20

3
0 0
0.3 0
1 0

0.3 0
0 0