Integral Points

Time limit3sMemory limit512 MB

Summary

Given n, output an integer radius r and n distinct integer points on the circle centered at the origin with radius r.

Level: Medium4 of 10
Topics: Number theory, Math, Implementation, Brute force
Solved: No attempts yet

Problem

A set of points is concyclic if all of them lie on the circumference of a single circle. Given an integer $n$ , find a circle centered at $(0, 0)$ whose circumference contains at least $n$ distinct integral points.

Note: integral points are points whose coordinates are both integers.

Input

The input is a single line containing a positive integer $n$ .

Output

Output $n + 1$ lines. The first line contains an integer $r$ , the radius of the circle. Each of the next $n$ lines contains two integers $x$ and $y$ such that the point $(x, y)$ lies on the circle.

Constraints

$1 \le n \le 1000$
This problem uses a special checker, so you do not have to output the minimum radius $r$ .
Each token in your output cannot exceed 30 characters.
Every point in your output must be unique.
The size of your code must be no greater than 256 kilobytes.

Examples2

Example 1
Input
```
1
```
Expected output
```
100
100 0
```
Example 2
Input
```
7
```
Expected output
```
5
5 0
0 5
-5 0
3 4
3 -4
-3 -4
-3 4
```