Description

In general, a positive integer can be decomposed into the sum of several positive integers.

For example, $1 = 1$, $10 = 1 + 2 + 3 + 4$, and so on. For a specific decomposition of a positive integer $n$, we call it “excellent” if and only if, under this decomposition, $n$ is split into several distinct powers of $2$ with positive integer exponents. Note that a number $x$ can be written as a power of $2$ with a positive integer exponent if and only if $x$ can be obtained by multiplying $2$ together a positive integer number of times.

For example, $10 = 8 + 2 = 2^3 + 2^1$ is an excellent decomposition. However, $7 = 4 + 2 + 1 = 2^2 + 2^1 + 2^0$ is not an excellent decomposition, because $1$ is not a power of $2$ with a positive integer exponent.

Now, given a positive integer $n$, you need to determine whether there exists an excellent decomposition among all decompositions of this number. If it exists, output a specific decomposition scheme.

Input Format

The input contains only one line with an integer $n$, which is the number to be checked.

Output Format

If there exists an excellent decomposition among all decompositions of this number, output each number in the decomposition from large to small, with a single space between adjacent numbers. It can be proven that after fixing the order of the numbers in the decomposition, the scheme is unique.

If no excellent decomposition exists, output -1.

6

4 2

7

-1

126

64 32 16 8 4 2

Hint

Explanation for Sample 1

$6 = 4 + 2 = 2^2 + 2^1$ is an excellent decomposition. Note that $6 = 2 + 2 + 2$ is not an excellent decomposition, because the $3$ numbers in the decomposition are not all distinct.

Constraints

• For $20\%$ of the testdata, $n \le 10$.
• For another $20\%$ of the testdata, $n$ is guaranteed to be odd.
• For another $20\%$ of the testdata, $n$ is guaranteed to be a power of $2$ with a positive integer exponent.
• For $80\%$ of the testdata, $n \le 1024$.
• For $100\%$ of the testdata, $1 \le n \le 10^7$.

Translated by ChatGPT 5