Coding is the closest thing we have to superpower ！
描述
给定一个整数n，如果存在某序列< a_0, a_1, a_2, ..., a_m >满足以下4个条件，则该序列称为n的加加链：
a_0 = 1
a_m = n
a_0 < a_1 < a_2 < ... < a_{m-1}
对于所有的k (1 \le k \le m) ，存在两个整数（可以相同）i, j (0 \le i, j \le k-1)使得 a_k=a_i+a_j 。
现在你的任务是，对于给定的n，构造最短的加加链。
输入
输入有多组数据，不超过10组。
每行给出一个整数n(1 \le n \le 100)。
输入0表示结束。
输出
输出加加链，两个整数用一个空格分开。
若有多解，输出数字尽量小的一组。
如对于5来说，“1 2 3 5”和“1 2 4 5”均可行，则输出“1 2 3 5”。
样例
输入
5 7 12 15 77 0
输出
1 2 3 5 1 2 3 4 7 1 2 3 6 12 1 2 3 5 10 15 1 2 4 5 9 18 36 41 77
标签