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 \leq N \leq 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.

-----Examples-----
Sample Input:
3
Sample Output:
0 0
40000000 0
0 40000000

Difficulty: competition

Starter code:

Solutions: