Addition Chains（教学范围）

题目描述

寻找从1严格递增到n的最短加法链。每个新项必须是任意两个此前项的和，两项允许相同。不同最短链任选，不限制必须含最后一项参与相加。

输入

多组，每行一个目标n，本地教学范围1≤n≤100；0结束。每个文件包含1..100个正目标。

输出

每个目标输出一行最短链，包含首项1与末项n。n=1输出1。采用逐项加法合法性与最短长度特判。

输入样例

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

本地修订说明

明确教学1..100、最多100组，保留原77等公开样例目标；最短性以独立BFS完整教学域证明，不能把仅last+x星形链当一般加法链。

本地评测数据为独立构造和核验的教学训练数据，非官方原版数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：明确教学1..100、最多100组，保留原77等公开样例目标；最短性以独立BFS完整教学域证明，不能把仅last+x星形链当一般加法链。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1443。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。