题目描述

给定一个目标整数 $n$，构造一个由正整数组成的序列，满足以下条件：

1. 序列的第一个元素为 $1$。
2. 序列的最后一个元素为 $n$。
3. 序列中的每个元素（除了第一个）都可以表示为该元素之前的某两个元素（可以是同一个元素）的和。

要求序列的长度尽可能短，若有多组最短序列，输出任意一个即可。

输入格式

输入包含多组测试数据。

每组数据占一行，包含一个整数 $n$。

当 $n = 0$ 时，输入结束。

输出格式

对于每组数据，输出一行，包含若干用空格分隔的整数，表示构造出的满足条件的序列。

样例

输入样例：

5
7
12
15
77
0

输出样例：

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

样例解释

以 $n=5$ 为例：
序列为 1 2 4 5

• 2 = 1 + 1
• 4 = 2 + 2
• 5 = 1 + 4

长度 4 是最短的。

其余样例类似。

数据范围

• $1 \le n \le 1000$
• 输入以 $n=0$ 结束

时空限制

• 时间限制：1 秒
• 空间限制：64 MB