Nowhere Money

In the town of Nowhere, money is made of coins and slots. There are two kinds of coins: size-1 and size-2. A size-2 coin is exactly twice as thick as a size-1 coin. People stack coins inside a slot and use the filled slot as money.

Slots come in many sizes. A slot of size $n$ can hold a stack of coins whose total thickness equals that of $n$ size-1 coins. Only a completely filled slot counts as valid money.

The value of a filled slot is the number of distinct ways it can be filled with coins. For example:

• A size-1 slot has only $1$ way: a single size-1 coin.
• A size-2 slot has $2$ ways: two size-1 coins, or one size-2 coin.
• A size-5 slot has $8$ ways: 1 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 2 2, 2 1 2, 2 2 1.

So a filled size-1, size-2, and size-5 slot is worth $1$, $2$, and $8$ monetary units respectively (the value depends only on the slot size, not on which coins are used or how they are arranged). Write $T(n)$ for the value of a filled slot of size $n$.

Mr. Thinktwice runs a grocery store. He noticed that customers prefer shops that hand back change in a convenient form, and from a small survey he learned that customers want their change built from slots under two rules:

1. The number of slots is as small as possible.
2. Every two slot sizes differ by at least $2$, so no two slots are the same size or adjacent sizes; this makes the slots easy to tell apart.

For a given amount of change, output a series of slot sizes that satisfies these rules, sorted in descending order. Every amount of change can be written as

$X = \sum_{i=1}^{n} T(s_i) = T(s_1) + \cdots + T(s_i) + \cdots + T(s_n), \qquad s_1 \gg s_2 \gg \cdots \gg s_n > 0$

where

• $X$ is the amount of change,
• $n$ is the number of slots,
• $s_i$ is the size of the $i$-th slot,
• $T$ maps a slot size to its value (the number of distinct ways to fill it), and
• $j \gg k$ means $j \ge k + 2$.

For example:

$10 = T(5) + T(2) = 8 + 2$

$1{,}000{,}000 = T(29) + T(25) + T(23) + T(11) + T(9) = 832040 + 121393 + 46368 + 144 + 55$

The input contains several amounts of change, one per line. Each amount is a positive integer not greater than $5 \times 10^{18}$. Input ends at end-of-file (EOF).

For each amount of change, print four lines:

1. the amount of change itself;
2. the slot sizes in descending order, separated by single spaces (every slot size is at most $90$);
3. the corresponding slot values, in the same order, separated by single spaces;
4. a blank line.