IQ Test

Time limit1sMemory limit512 MB

Summary

Given n up to 10^18, output at most 43 operations x^2 - y on a set starting with 0, 1, 2 so that n ends up in the set.

Level: Medium7 of 10
Topics: Math, Bit manipulation, Implementation
Solved: No attempts yet

Problem

You are given a set $S$ of integers. Initially, $S$ contains $0$ , $1$ , and $2$ .

You can perform zero or more steps. On each step, you choose two elements (possibly equal) $x$ and $y$ such that $x \in S$ and $y \in S$ , and insert the number $x^2 - y$ into the set $S$ .

You cannot perform more than 43 steps.

Your task is to get the integer $n$ in your set.

Input

The first line contains a single integer $n$ ( $0 \le n \le 10^{18}$ ), the number you have to get in the set.

Output

For each step, print $x$ and $y$ on a separate line. The condition $0 \le x^2 - y \le 10^{18}$ must be satisfied.

The number of steps must be at most 43. You do not have to minimize it. If there are several possible solutions, print any one of them.

Examples2

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