3의 거듭제곱

음이 아닌 정수 지수를 갖는 $3$의 거듭제곱을 모두 모은 집합 $S$를 생각하자.

$S = \{3^0, 3^1, 3^2, 3^3, \dots\} = \{1, 3, 9, 27, 81, \dots\}$

$S$의 모든 부분집합을 각 부분집합에 속한 원소들의 합을 기준으로 오름차순으로 정렬한다. 서로 다른 $3$의 거듭제곱들의 합은 절대로 같아질 수 없으므로, 이 정렬 순서는 유일하게 정해진다. 합이 $0$인 공집합이 가장 앞에 온다.

이 정렬 순서에서 $n$번째 부분집합을 구하는 프로그램을 작성하시오.

입력은 여러 줄로 이루어진다. 각 줄에는 정수 $n$이 하나씩 주어진다. $n$은 $19$자리를 넘지 않는 양의 정수이며, 즉 $1 \le n \le 10^{19} - 1$이다. 입력의 마지막 줄에는 $0$이 주어지고, 이 줄은 처리하지 않는다.

각 $n$에 대해, 정렬된 부분집합들 중 $n$번째 집합을 한 줄에 출력한다. 집합은 원소를 오름차순으로 나열하여 { 원소1, 원소2, ... } 형식으로 출력한다. 여는 중괄호 뒤와 닫는 중괄호 앞에는 공백을 하나씩 두고, 원소 사이는 쉼표와 공백(, )으로 구분한다. 공집합은 { }로 출력한다.