페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8297
서브태스크

x^2-y 1s 1024MB

문제

정수로 이루어진 집합 S에는 세 개의 원소 {0,1,2}가 들어있다.

아래와 같은 동작을 반복하여 실행시켜 정수 N를 집합 S의 원소로 만드는 과정을 출력하는 프로그램을 작성하시오.

  1. 집합 S에서 두 원소 x와 y를 선택한다.

  2. 집합 S에 x^2-y를 추가한다.

반드시 위 동작은 43번 이내에 완료되어야 한다.


입력

첫 줄에 정수 N이 주어진다. (1 \le N \le 10^{18})


출력

각 동작마다 선택된 두 정수 x와 y를 공백으로 구분하여 출력한다.

  • 반드시 0 ≤ x^2 − y ≤ 10^{18}이 만족되어야 한다.


부분문제

번호 점수 조건
#110점

N \le 10

#220점

N \le 100

#330점

N \le 1000

#440점

추가 제약 조건 없음


예제 #1

3
2 1

예제 #2

6
2 1
3 3

예제 #3

10
2 0
2 1
3 3
4 6


로그인해야 코드를 작성할 수 있어요.