Abandoned Skyline

Madeline recalls a long‐ago trip to an abandoned city whose skyline was formed by buildings of very special heights. In that city every building’s height can be expressed in the form \(2^i \times 3^j\) with nonnegative integers \(i,j\) satisfying \(i+j\ge1\). Moreover, the skyline is aesthetically pleasing: no two buildings have heights such that one is an integer multiple of the other (note that a 1× multiple is included in this relation). Many years later, all Madeline remembers is that the sum of all building heights is exactly n.

Your task is: given an integer n (guaranteed to be representable as a sum of some allowed numbers satisfying the above divisibility‐free condition), output any valid skyline. A valid skyline is defined as a set \(S\) of distinct allowed numbers (each of the form \(2^i\times 3^j,\; i,j\ge0,\; i+j\ge1\)) such that

[ \sum_{x\in S} x = n, \quad \text{and for any distinct } a,b\in S, ; a\ \text{is not an integer multiple of } b. ]

If no valid skyline exists, print -1 instead. When a valid skyline exists, the output format is as follows:

• The first line contains an integer k representing the number of buildings.
• The second line contains k space‐separated integers denoting the heights of the buildings.

Note: It is guaranteed that the input n is such that a valid skyline exists. If there are multiple answers, you may output any one of them.

inputFormat

The input consists of a single integer n on one line, where \(2 \le n \le 10^9\) (in our test cases, n will be small enough to allow a backtracking solution).

You can assume that there exists at least one valid skyline.

outputFormat

If a valid skyline exists, output it in the following format:

• First line: an integer k representing the number of buildings.
• Second line: k space‐separated integers indicating the building heights.

If no valid skyline exists, output a single line containing -1.

sample

5

2
2 3