Four Equidistant Points on a Grid ~ WildLife-TK

The manhattan distance between two points

$P_{1} (x_{1}, y_{1})$ and $P_{2} (x_{2}, y_{2})$ is given by $d (P_{1}, P_{2}) = | x_{2} - x_{1} | + | y_{2} - y_{1} |$ .

In other words, manhattan distance is the minimum number of moves required to reach $P_{2}$ from $P_{1}$ if, in each move, you are allowed to travel one unit along the $X$ -axis or one unit along the $Y$ -axis.

You are given an integer $D$ . Find four points $(P_{1}, P_{2}, P_{3}, P_{4})$ with integer coordinates, such that:

The absolute value of both $X$ and $Y$ coordinates of all points is at most $10^{9}$ .
The manhattan distance between any pair of points is $D$ . More formally, $d (P_{i}, P_{j}) = D$ for all $1 \leq i < j \leq 4$ .

If such set of points do not exist, print -1. If there are multiple solutions, you may print any.

Note: It is guaranteed that whenever there exists a solution, there exists one in which all points have coordinates with absolute values not more than $10^{9}$ .

Input Format

The first line contains a single integer, $D$ - as per the problem statement.

Output Format

If there is no solution, print in a single line the integer -1.
Otherwise print $4$ lines. The $i^{t h}$ line, should contain two space separated integers, $X_{i} Y_{i}$ , the coordinates of the point $P_{i}$ , such that $0 \leq | X_{i} |, | Y_{i} | \leq 10^{9}$ .

Constraints

$1 \leq D \leq 10^{5}$

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1

Sample Output 1

Explanation

The following sample output for this testcase is not correct, but is only provided to clarify the output format

The points in the solution are $P_{1} (0, 1), P_{2} (1, 2), P_{3} (2, 3)$ and $P_{4} (3, 4)$ . $d (P_{1}, P_{2}) = | 0 - 1 | + | 1 - 2 | = 2$ but $d (P_{1}, P_{3}) = | 0 - 2 | + | 1 - 3 | = 4$ . As $d (P_{1}, P_{2}) \neq d (P_{1}, P_{3})$ , the solution is incorrect.

A correct solution will satisfy $d (P_{1}, P_{2}) = d (P_{1}, P_{3}) = d (P_{1}, P_{4}) = d (P_{2}, P_{3}) = d (P_{2}, P_{4}) = d (P_{3}, P_{4})$

A correct sample output is not provided so as to not reveal any hints about the solution.

Sample Input 2

Sample Output 2

-1

Explanation

You may verify that for $D = 1$ , there are no set of points $P_{1}, P_{2}, P_{3}, P_{4}$ as per the problem statement. This output is correct.