# 2155. Addition Chains

An addition chain for $n$ is an integer sequence ${a_0, a_1,a_2,\ldots,a_m}$ with the following four properties:

• $a_0 = 1$
• $a_m = n$
• $a_0 < a_1 < a_2 < \ldots < a_{m-1} < a_m$
• For each $k$ ($1 \le k \le m$) there exist two (not necessarily different) integers $i$ and $j$ ($0 \le i, j \le 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$.

### 输入格式

The input will contain one or more test cases. Each test case consists of one line containing one integer $n$ ($1 \le n \le 100$). 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.

### 样例

Input
5
7
12
15
77
0

Output
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


14 人解决，16 人已尝试。

20 份提交通过，共有 29 份提交。

3.9 EMB 奖励。