Hide

Problem D
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 \leq N \leq 400\, 000$, 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.

Sample Input 1 Sample Output 1
3
0 0
40000000 0
0 40000000
Sample Input 2 Sample Output 2
4
5 5
0 0
5 0
0 5

Please log in to submit a solution to this problem

Log in