Hell of Optimizing Geometric Construction

One day, dnialh mentioned that optimizing geometric construction perfectly is not possible. Oh, very well. You will see about that.

You are given a positive integer $n$ such that $2 \le n \le 1\,320$. Please find a sequence of $n$ points on the plane, $X_1,X_2,\cdots,X_n$, satisfying the following constraints.

• The coordinates of each point are integers in the range $[-1\,000,1\,000]$.
• No two points share the same coordinates.
• For each $1 \le i \le n$, the closest point to $X_i$ other than $X_i$ itself is unique. Let the index of this unique point be $f(i)$.
• Let $p$ be a sequence of $n$ integers defined by $p_1=1$ and $p_{i+1}=f(p_i)$ for $1 \le i < n$. Then, $p$ is a permutation of $1,2,\cdots,n$.

It is proven that such a sequence of points exists under the constraints of this task.

A positive integer $n$ is given on one line. ($2 \le n \le 1\,320$)

Output $n$ lines. The $i$-th line must contain $x_i$ and $y_i$, the coordinates of $X_i$, separated by a space. ($-1\,000 \le x_i,y_i \le 1\,000$)

In the samples, $n=4$ and $X=[(-2,-2),(1,2),(-2,2),(2,1)]$.

Here, $f(i)$ is determined as follows.

• Other than $X_1$, the unique closest point to $X_1$ is $X_3$. Therefore, $f(1)=3$.
• Other than $X_2$, the unique closest point to $X_2$ is $X_4$. Therefore, $f(2)=4$.
• Other than $X_3$, the unique closest point to $X_3$ is $X_2$. Therefore, $f(3)=2$.
• Other than $X_4$, the unique closest point to $X_4$ is $X_2$. Therefore, $f(4)=2$.

Now, one can manually verify that the resultant sequence $p=[1,3,2,4]$ is a permutation of $1,2,3,4$. Therefore, the sequence of points satisfies the constraints.