Programming Problem #17
"Fast Exponentiation"

The obvious way to compute x^n when n is a positive integer is to compute the product 
 x * x * ... * x * x
\___________________/
          |
       n times
which requires (n-1) multiplications. This is equivalent to computing the sequence of products x^1, x^2, ..., x^n, with the last product being the desired result. This sequence has the property that any element in the sequence is either the product of two previous elements or the square of a previous element. It is usually possible to construct much shorter sequences with this property that compute x^n; for example, when n=15 the sequence x^1,x^2,x^4,x^5,x^10,x^15 requires only five multiplications. In fact, this sequence is optimal in the sense that no shorter sequence will compute x^15, although there are at least three other sequences of the same length.

Note: Many textbooks have an algorithm for computing product sequences based on the following recurrence relation.

However, in general the resulting sequences are not optimal. For example, when n=15 these relations yield the sequence x^1,x^2,x^3,x^6,x^7,x^14,x^15 which is longer than the one given above.

The input consists of one or more values of n, each left-justified on a line by itself. Each value of n will be an integer between 1 and 80, inclusive. For each value of n, output an optimal sequence of products using the format shown in the examples. (If there is more than one optimal sequence, output any of them.)

Input must be read from the file "prob17.in", and output must be written to the file "prob17.out". All output to the screen will be ignored.

Example Input

<BOF>
15
23
<EOF>

Example Output

1 2 4 5 10 15
1 2 4 5 9 18 23
A version of this problem originally appeared in the 1986 Rocky Mountain regionals.

Dr. Eric Shade