题目描述

一个用于$n$的加法链是一个满足以下四个条件的整数序列：

1. $a_0 = 1$
2. $a_m = n$
3. $a_0 < a_1 < a_2 < \cdots < a_{m-1} < a_m$
4. 对于每个$k$（$1 \leq k \leq m$），存在两个（不一定不同的）整数$i$和$j$（$0 \leq i, j \leq k-1$），使得$a_k = a_i + a_j$。

给定一个整数$n$，你的任务是构造一个长度最短的加法链。如果有多个这样的序列，输出任意一个即可。

例如，当要求为$5$构造加法链时，$<1, 2, 3, 5>$和$<1, 2, 4, 5>$都是有效的解。

输入格式

输入包含一个或多个测试用例。每个测试用例占一行，包含一个整数$n$（$1 \leq n \leq 100$）。输入以$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