Carrot breeding

Time limit8sMemory limit512 MB

Summary

Place the fewest lattice points in the square so that each point lies on exactly N lines through at least two points, or report -1 if impossible.

Level: Hard8 of 10
Topics: Geometry, Combinatorics
Solved: No attempts yet

Problem

Carrots like to breed. A rabbit decided to grow carrots in its field. The field is a square (boundary included) whose diagonal runs from (0, 0) to (1000000000, 1000000000). Every day, the rabbit waters once along every straight line that passes through at least 2 carrots.

The carrots believe they breed best when each one is watered exactly $N$ times a day, so they arrange themselves in the field to meet that condition. Carrots can only be placed on lattice points inside the field. If several arrangements meet the condition, choose the one with the fewest carrots. Output one arrangement that meets the condition. If no such arrangement exists, output -1.

Input

The input is given in the following format:

$N$

Output

If no valid arrangement exists, print -1 on one line.

Otherwise, let $K$ be the number of carrots and print in the following format: $K$ $x_1$ $y_1$ ... $x_K$ $y_K$

Constraints

$N$ is between 1 and 1,000,000, inclusive.

Examples2

Example 1
Input
```
4
```
Expected output
```
4
0 0
1 0
2 0
1 1
```
Example 2
Input
```
6
```
Expected output
```
4
0 0
0 1
1 0
1 1
```