시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 7 7 6 100.000%

문제

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 ∈ S and y ∈ S, and insert the number x2 − y into the set S.

You can not perform more than 43 steps.

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

입력

The first line contains a single integer n (0 ≤ n ≤ 1018), the number you have to get in the set.

출력

For each step, print x and y on a separate line. The condition 0 ≤ x2 − y ≤ 1018 must be satisfied.

The number of steps must be at most 43. Note that you don’t have to minimize it. If there are several possible solutions, print any one of them.

예제 입력 1

5

예제 출력 1

1 1
2 1
2 0
3 4

예제 입력 2

7

예제 출력 2

1 1
2 1
3 2