$描述$
考虑所有3的非负整数次幂组成的集合。

$S = \{ 1, 3, 9, 27, 81, \ldots \}$

将集合$S$的所有子集按元素和的值排序，形成一个序列。问题很简单：找到该序列中第$n$个位置的集合，并按元素升序输出该集合。

$输入$
输入的每一行包含一个正整数$n$，$n$的位数不超过19位。输入的最后一行是0，这一行不需要处理。

$输出$
对于每一行输入，输出单独的一行，按照上述描述显示第$n$个集合，格式与样例输出一致。

输入数据1

1
7
14
783
1125900981634049
0

输出数据1

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