Problem Description

This problem is translated from PA 2022 Round 2 Muzyka pop 2.

You may still remember that Matthew likes pop music. He has just written a new song, and the only thing missing is an ending.

Matthew wants this ending to contain some non-empty notes, where each note is described by its loudness, and loudness is a positive integer. Matthew may use notes of any loudness, but the purpose of the ending is to gradually fade out the whole song—therefore, the loudness of the notes in the ending must form a strictly decreasing sequence.

As you may know or remember, a good beat is important in pop music. This time, Matthew found that the beat value of a note with loudness $x$ is the number of $1$ bits in the binary representation of $x$. Considering the rest of the song, he wants the sum of the beat values of all notes in the ending to be exactly $n$.

Help him find a correct sequence of note loudness values. It can be proven that there is always at least one sequence that satisfies the conditions, so your task is to output the lexicographically smallest sequence.

Note: For two sequences of numbers $A$ and $B$, if at the first position where they differ, the integer in $A$ at that position is smaller than the integer in $B$ at that position, then $A$ is lexicographically smaller than $B$. If there is no such position, then the shorter sequence is lexicographically smaller. For example, the sequence $[1, 10000000]$ is lexicographically smaller than $[2,2]$, the sequence $[4, 2, 20, 30, 40]$ is lexicographically smaller than $[4, 2, 100, 1]$, and the sequence $[5,4,3,2]$ is lexicographically smaller than $[5,4,3,2,1]$.

Input Format

Input one line with one integer $n$, the required sum of beat values of the notes in the sequence.

Output Format

The first line contains an integer $k$, the length of the sequence you found.

The second line contains $k$ positive integers, the sequence you found. This sequence should be lexicographically smallest and strictly decreasing, and the total number of $1$ bits in the binary representations of these positive integers must be exactly $n$.

3

2
3 1

10

6
7 5 4 3 2 1

Hint

For $100\%$ of the testdata, it holds that:

$1\le n\le 10 ^ 6$。

Translated by ChatGPT 5