시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 17 17 73.913%

문제

다음과 같이 모든 음이 아닌 3의 제곱수가 들어있는 집합이 있다.

S = {1, 3, 9, 27, 81, ...}

S의 모든 부분집합을 구한 뒤, 이 집합을 가지고 있는 원소값의 합으로 오름차순 정렬했을 때, n번째 집합을 구하는 프로그램을 작성하시오.

입력

입력을 여러 개의 줄로 이루어져 있고, 각 줄에는 n이 주어진다. n은 19자리를 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0이 있다. 

출력

각 입력에 대해서, n번째 집합을 예제 출력 형식과 같게 출력한다.

예제 입력

1
7
14
783
1125900981634049
0

예제 출력

{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }

힌트