Irrational pairwise distances

For a given natural number N it is required to construct the set of N points of the Cartesian plane such that

coordinates of points are integer;
a distance between any two points of the set is irrational;
any three points of the set does not lie on one line.

Specifications

Input

The only line of the input file contains a natural number N ≤ 1000, defining the number of points in a set.

Output

In the output file you should write coordinates of points of a constructed set (each points should be in single line, its coordinates should be separated by space). Coordinates of points can not exceed 1000000 by absolute value. It is provided that there exists such set. If there are many sets satisfying conditions, you can output any of them.

Problem information

Time Limit: 0.5 seconds
Memory Limit: 64 MB
Balls for the passed test: 3.0303
Complexity: 44% 14/25
Autor: А.Лунев
Source: Зимние сборы в Харькове 2010 День 1

Example

Example input

Sample 1
1

Sample 2
2

Sample 3
3

Example output

Sample 1
1000000 -1000000

Sample 2
0 0
1 1

Sample 3
0 0
1 1
-1 2

← Indivisibility of binomial coefficients

Problems

Minimaximal matching →