Problem G
Closest Pair (Uniform)

Input

Input contains several test cases. Each test case begins with an integer $n$ ($2 \le n \le 100\, 000$). Then follows a list of $n$ points, one per line, each of the form $x$ $y$. Coordinates are floating point values with at most $2$ decimals and absolute value bounded by $100\, 000$. You may assume that the points have been generated by picking $x$ and $y$ independently uniformly at random in the interval $[-100\, 000, 100\, 000]$. The input is terminated by a case beginning with $0$.

Warning! This problem has a largish input file.

Output

For each test case, output any closest pair of the input points, on the form $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$.

2
1.12 0
0 0.51
3
158 12
123 15
1859 -1489
3
21.12 -884.2
18.18 43.34
21.12 -884.2
0

0.0 0.51 1.12 0.00
123 15 158 12.00
21.12 -884.20 21.12 -884.20