As you may remember, Mateusz loves pop music. He has just composed a new piece and only needs to arrange a suitable ending for it.

Mateusz wants the ending of his piece to consist of a non-empty sequence of notes, where each note can be described by its volume, which is a positive integer. Mateusz can use notes of arbitrarily high volumes, but the purpose of the ending is to gradually fade out the piece – for this reason, the volumes of the notes in the ending must form a strictly decreasing sequence.

As you may know or remember, good bits are important in pop music. This time, Mateusz has decided that a note with volume $x$ has a bit power equal to the number of set bits (population count) in the binary representation of $x$. Considering the rest of the piece, he has determined that the sum of the bit powers of the notes in the ending must be exactly $n$.

Help him find a suitable sequence of note volumes. It can be proven that at least one such sequence always exists, so your task is to find the lexicographically smallest one.

Note: We say that a numerical sequence $A$ is lexicographically smaller than a numerical sequence $B$ if, at the first position where the sequences differ, $A$ contains a smaller number than $B$. If no such position exists, then $A$ is lexicographically smaller than $B$ if $A$ is shorter than $B$. For example, the sequence $[1, 10000000]$ is lexicographically smaller than the sequence $[2, 2]$, the sequence $[4, 2, 20, 30, 40]$ is lexicographically smaller than the sequence $[4, 2, 100, 1]$, and the sequence $[5, 4, 3, 2]$ is lexicographically smaller than the sequence $[5, 4, 3, 2, 1]$.

Input

The only line of standard input contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the required sum of the bit powers of the notes in the sought sequence.

Output

The first line of standard output should contain a single integer $k$, representing the length of the sought sequence.

The second line of standard output should contain $k$ positive integers – the lexicographically smallest, strictly decreasing sequence whose elements have a total of exactly $n$ set bits in their binary representation.

Examples

Input 1

3

Output 1

2
3 1

Input 2

10

Output 2

6
7 5 4 3 2 1

Note

In the first example test case, other valid sequences include, for example, $[3, 2]$, $[7]$, or $[4, 2, 1]$, but the sequence $[3, 1]$ is the lexicographically smallest possible. Note that, for example, the sequences $[1, 3]$, $[3, 1, 0]$, and $[2, 2, 2]$ are not valid sequences because they are not strictly decreasing or contain non-positive elements.