Bear and Oveflow Points

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
In competitive programming, one of the common mistakes is using a variable type that stores too few bits, which leads to overflows and underflows. We will focus on the "unsigned int" type, which makes all calculations modulo 2^{32}, always giving a nonnegative result between 0 and 2^{32}  1, inclusive. Sample calculations on type "unsigned int" are:
7  5 = 2, 5  7 = 4294967294, 5 * 1,000,000,000 = 705032704
Limak wants to become a great coder. Right now he learns the computional geometry. He already knows that three points (ax, ay), (bx, by), (cx, cy) are collinear if and only if:
(bx  ax) * (cy  ay) = (by  ay) * (cx  ax)
Without thinking which type to use, Limak wrote the following C++ function:
typedef unsigned int UI;
bool areCollinear(UI ax, UI ay, UI bx, UI by, UI cx, UI cy) {
return (bx  ax) * (cy  ay) == (by  ay) * (cx  ax);
}
If you are more familiar with Python, you can assume that he wrote:
M = 2 ** 32
def subtract(a, b):
ans = a  b
if ans < 0:
ans += M
return ans
def mul(a, b):
return a * b % M
def areCollinear(ax, ay, bx, by, cx, cy):
return mul(sub(bx, ax), sub(cy, ay)) == mul(sub(by, ay), sub(cx, ax))
To show Limak how important it is to watch for overflows, you must find any set of N distinct points that:
 Any three distinct points in any order would be treated as collinear by Limak's function.
 None three points are collinear (what implies that points are distinct).
 Coordinates are nonnegative integers not exceeding 10^{6}.
If there are many solutions (valid sets of points), you can print any of them. There exists at least one solution for every N allowed by the constraints.
Input
The only line of the input contains an integer N denoting the required number of points.
Output
Print N lines. The ith of them should contain two spaceseparated integers x_{i} and y_{i}, denoting coordinates of the ith point. If there are many solutions, you can print any of them.
Remember that one of requirements is 0 ≤ x_{i}, y_{i} ≤ 10^{6}.
Constraints
 3 ≤ N ≤ 10
Subtasks
 Subtask #1 (50 points) 3 ≤ N ≤ 5
 Subtask #2 (50 points) original constraints
Example
Input1: 3 Output2: 106732 139820 210379 490375 42 483426 Input2: 4 Output2: 580981 431795 914958 554338 518360 23016 441824 483616
Explanation
Test case 1. The provided function areCollinear() should return True for the found three points given in any order (there are 3! = 6 possible orders of 3 points). Let's analyze the evaluation of areCollinear(42, 483426, 106732, 139820, 210379, 490375):
Without any overflow errors, the calculations would be:
(bx  ax) * (cy  ay) = (106732  42) * (490375  483426) = 741388810
(by  ay) * (cx  ax) = (139820  483426) * (210379  42) = 72273055222
And indeed numbers 741388810 and 72273055222 are equal modulo 2^{32}. Hence areCollinear would think that they are collinear.
Author:  errichto 
Tester:  errichto 
Editorial  https://discuss.codechef.com/problems/OVERPNT 
Tags  errichto ltime45 mediumhard 
Date Added:  23022017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, D, ERL, FORT, FS, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions