18665번 - IQ Test 스페셜 저지다국어

문제

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 x² − 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 ≤ 10¹⁸), the number you have to get in the set.

출력

For each step, print x and y on a separate line. The condition 0 ≤ x² − y ≤ 10¹⁸ 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.

제한

힌트