H. Hell of Optimizing Geometric Construction
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \lt 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.

Input

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

Output

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$$$)

Example
Input
4
Output
-2 -2
1 2
-2 2
2 1
Note

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.