Chef prepares the following problem for a programming contest:
You are given N points with integer coordinates (-1000 ≤ xi, yi ≤ 1000). No two points collide and no three points are collinear. For each of the 2N-1 non-empty subsets of points, find the size (the number of points) of its convex hull. Print the sum of those sizes.
Chef has already prepared some tests for this problem, including a test with the maximum possible answer. He now needs a test with a quite small answer (but not necessarily the minimum possible one). Forgiven N, your task is to find any valid set of N points for which the answer doesn’t exceed 4 * 1015 (4,000,000,000,000,000).
The only line of the input contains a single integer N, denoting the number of points.
Print exactly N lines. The i-th line should contain two integers xi and yi, denoting coordinates of the i-th point.
The printed set of points must satisfy all the given conditions. At least one such set exists for every N allowed by the constraints given below.
Note: Remember that you don’t print N in the first line.
- 2 ≤ N ≤ 50
Input: 5 Output: -150 150 150 150 -150 -150 150 -150 11 13
Let’s analyze sizes of convex hulls for the provided output. There are 25-1 non-empty sets of points.
- There are 5 sets of points that consist of only 1 point each. The convex hull of each of those sets has size 1.
- Similarly, 10 sets of points consist of 2 points each, and the size of each of their convex hulls is 2.
- Similarly, there are 10 sets with 3 points each, and the size of each of their convex hulls is 3.
- The set with points (-150, -150), (-150, 150), (150, 150), (11, 13) has a convex hull of size 3. You can note that the point (11, 13) is inside the triangle formed by the other three points.
- The set with points (-150, 150), (150, 150), (150, -150), (11, 13) has a convex hull of size 3 as well.
- There are 3 other sets with 4 points, and for each of them, the convex hull has size 4.
- Finally, the set with all 5 points has a convex hull of size 4.
The sum of sizes of convex hulls is (5 * 1) + (10 * 2) + (10 * 3) + 3 + 3 + (3 * 4) + 4 = 5 + 20 + 30 + 6 + 12 + 4 = 77, which obviously doesn’t exceed 4 * 1015.