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 |
