Minimum Bucket Set

Farmer John needs to measure out exactly \(Q\) quarts of his best milk to fill a large bottle in order to sell it. Since his customers order various amounts and he never wants to make a mistake, he wishes to set up a system of buckets such that, without any partial fills or transferring milk between buckets, every integer amount from 1 to \(Q\) quarts can be measured exactly. The only allowed operation is to go to his milk pool, completely fill a bucket and then pour its entire contents into the bottle. Note that once a bucket is filled and poured, its milk cannot be re‐poured or partially used in another measurement.

The hardware store sells buckets of various capacities (in quarts), and all buckets cost the same. However, because Farmer John must carry the buckets home, he wishes to purchase as few buckets as possible. In other words, he wants to choose a set \(S = \{s_0,s_1,\dots,s_{k-1}\}\) of distinct bucket capacities (in quarts) so that by using each bucket at most once per measurement (i.e. by selecting an appropriate subset of \(S\)) he can measure every integer from 1 up to \(Q\), and the total number of buckets \(k\) is minimized.

It can be shown that a bucket system \(S = \{s_0,s_1,\dots,s_{k-1}\}\) will allow measuring every integer quantity from 1 up to \(\sum_{i=0}^{k-1} s_i\) if and only if

[ \begin{cases} s_0=1,\ s_i\leq \left(\sum_{j=0}^{i-1}s_j\right)+1 \quad \text{for } i\ge 1. \end{cases} ]

Among all bucket systems that allow measuring every amount from 1 to \(Q\) (that is, systems with \(\sum_{i=0}^{k-1} s_i\ge Q\)), Farmer John wants one with the minimum number \(k\) of buckets. If more than one such system exists, he chooses the lexicographically smallest one when both systems are sorted in ascending order (i.e. compare the smallest bucket in each system; if they are the same, compare the second smallest, and so on).

A well‐known fact is that no system of \(k\) buckets can measure more than \(2^k-1\) quarts. Hence the minimum number of buckets required is the smallest integer \(k\) such that \(2^k-1\ge Q\). However, the canonical system \(\{1,2,4,8,\dots,2^{k-1}\}\) (which achieves a total of \(2^k-1\)) need not be lexicographically optimal. For example, if \(Q=12\) then since \(2^4-1=15\ge 12\), one can use 4 buckets. The canonical set would be \(\{1,2,4,8\}\) but note that the system \(\{1,2,3,6\}\) also allows measuring every amount from 1 to 12 (since </em>1 \(\le\) 1, 2 \(\le\) 1+1, 3 \(\le\) 1+2, and 6 \(\le\) 1+2+3+1=7</em>) and is lexicographically smaller than \(\{1,2,4,8\}\) (because after sorting both in ascending order, the third element 3 is smaller than 4).

Your task is to compute the lexicographically smallest set of bucket capacities (in ascending order) with as few buckets as possible such that every integer quantity from 1 to \(Q\) can be measured, that is, for every integer \(x\) with \(1\le x\le Q\) there is a subset of the buckets whose capacities sum exactly to \(x\). It is guaranteed that for all test cases there exists at least one solution.

Input

A single integer \(Q\) (\(1\le Q\le 20\,000\)).

Output

Output the capacities of the buckets in the lexicographically smallest optimal set (in ascending order), separated by a single space.

inputFormat

The input consists of one integer \(Q\) (\(1\le Q\le 20\,000\)).

outputFormat

Output a single line containing the bucket capacities (in ascending order) separated by a space.

sample

1

1