Powers of Three

Time limit1sMemory limit128 MB

Summary
Given n, list the elements of the n-th smallest subset of powers of 3 when subsets are ordered by their sums.
Level

Medium6 of 10

Topics
Math, Combinatorics, Bit manipulation, Implementation
Solved
No attempts yet

Problem

Consider the set SS containing every power of 33 with a non-negative integer exponent.

S={30,31,32,33,… }={1,3,9,27,81,… }S = \{3^0, 3^1, 3^2, 3^3, \dots\} = \{1, 3, 9, 27, 81, \dots\}

Sort all subsets of SS in ascending order by the sum of the elements in each subset. Because the sum of distinct powers of 33 is always unique, this ordering is uniquely determined. The empty set, whose sum is 00, comes first.

Write a program that finds the nn-th subset in this order.

Input

The input consists of several lines. Each line contains a single integer nn. nn is a positive integer with at most 1919 digits, that is, 1≤n≤1019−11 \le n \le 10^{19} - 1. The last line contains 00, which is not processed.

Output

For each nn, print the nn-th set of the sorted order on its own line. List the elements in ascending order in the format { e1, e2, ... }, with a single space just inside each brace and the elements separated by a comma and a space (, ). Print the empty set as { }.

Examples1

  1. Example 1

    Input
    1
7
14
783
1125900981634049
0
    Expected output
    { }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }