Problem H
Association for Convex Main Office

You are the boss of ACM (Association for Convex Main Office), an upstanding company with a single goal of world domination.

Today, you have decided to move your main office from Helsinki to Singapore. You have purchased a square-shaped land in Singapore, represented as a square on a two dimensional Cartesian plane. The size of your land is $(4\cdot {10}^7)\times (4\cdot {10}^7)$.

After much deliberation, your engineers have devised the optimal shape of your new main office. It will be a grand building, shaped as a convex polygon on the two dimensional grid (a convex polygon is a simple polygon such that for any two of its vertices, the straight line connecting the two vertices is completely inside the polygon). More specifically, your main office is represented by a polygon with at least $3$ vertices such that:

• Each vertex is located on a lattice point (lattice points are points which coordinates are integers).

• The coordinates of all vertices are between $0$ and $4\cdot {10}^7$, inclusively.

• All vertices are located on distinct points.

• No three vertices are collinear (that is, no three vertices should be on a line).

• All the vertices form a convex polygon in some order.

It is a known fact that the number of vertices composing your main office is very important. A lucky number would positively influence the chance of success for all of your evil missions. Thus, given $N$, the number of vertices of the main office, can you generate any one possible way to construct your main office? That is, you should output any possible set of $N$ locations of the $N$ vertices of your main office that has the properties described earlier.

Input

The first line contains a non-negative integer $3\le N\le 400000$, giving the number of vertices your main office should have.

Output

Output exactly $N$ lines. Each line consists of two integers $0\le x,y\le 4\cdot {10}^7$, denoting the coordinates of a vertex making up your main office. The coordinates can be given in any order and must adhere to your main office’s restrictions as described in the problem statement.

Warning: Your program will have to write lots of output. Please use fast output routine to minimize the risk of getting a ‘Time Limit Exceeded’ verdict.

3

0 0
40000000 0
0 40000000

4

5 5
0 0
5 0
0 5