Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3290
Longest Subtrahend Sequence

Time Limit: 1 Second      Memory Limit: 32768 KB      Special Judge

This problem is quite simple ^_^

You are given one integer n. In order to decrease n down to zero, you may choose a sequence of subtrahend. When n becomes zero after several steps, all the subtrahends form a sequence K0, K1, ..., Ks-1(s is the number of subtration before you change n to 0). We call a subtrahend sequence valid if and only if the sequence satisfys the two certain conditions:

  • 1 <= K0 <= n
  • 1 <= Ki < Ki-1 / 2 (1 <= i <= s - 1)
    If we cannot change n to zero after subtracting all the elements of a sequence S successively, we never consider S valid. It is easy to conclude that the length of the subtrahend sequence may vary from each other. Could you help me to construct a valid sequence with a maximal length?


    The input contains multiple test cases, each test case only contains a single integer n (1 <= n <= 263-1).


    Output for each test case contains two lines. One integer in the first line indicating the maximal valid subtrahend sequence length. In the second line, there should be the subtrahend sequence you constructed. Seperate the subtrahends with a single space. Seperate each case with a single line.

    Sample Input


    Sample Output

    7 2
    7 3 1

    Author: HE, Xing
    Source: ZOJ Monthly, January 2010
    Submit    Status