2205번 - 저울 추 만들기 스페셜 저지

문제

질량(또는 무게)가 1, 2, 3, …, n인 납덩어리가 있고, 질량이 1, 2, 3, …, n인 주석덩어리가 있다. 각각의 질량을 갖는 덩어리들은 1개씩밖에 없다. 이제 이 납덩어리와 주석덩어리를 한개씩 녹여 합쳐서 질량이 2의 거듭제곱이 되는 저울추를 n개 만들려고 한다.

질량이 x인 납덩어리와 질량이 y인 주석덩어리를 합친 경우를 (x, y)로 나타내기로 하고, 다음과 같이 녹여 합친 경우를 보자. (1, 1), (2, 2), (3, 5), (4, 4), (5, 3). 각각의 저울추의 질량은 2, 4, 8, 8, 8이 되고 이들은 모두 2의 거듭제곱 꼴이 된다.

n이 주어졌을 때 저울추 n개를 만드는 방법을 하나 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다.

출력

첫째 줄부터 각 줄에 질량이 1인 납덩어리와 합친 주석덩어리의 질량, 질량이 2인 납덩어리와 합친 주석덩어리의 질량, 질량이 3인 납덩어리와 합친 주석덩어리의 질량, …을 n개의 줄에 출력한다.

제한

힌트