Addition Chains

题号：NC51018
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

An addition chain for n is an integer sequence <a0>with the following four properties:

$a_0 = 1$
$a_m = n$
$a_0 \lt a_1 \lt a_2 \lt \dots \lt a_{m-1} \lt a_m$
For each $k (1\leq k\leq m)$ there exist two (not necessarily different) integers i and j ( $0\leq i, j \leq k-1$ ) with $a_k=a_i+a_j$

You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.</a0>

输入描述:

The input will contain one or more test cases. Each test case consists of one line containing one integer  Input is terminated by a value of zero (0) for n.

输出描述:

For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.
Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.

示例1

输入

复制

输出

复制

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77