#1025. Addition Chains

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: Mars_Dingdang

题目描述

From POJ 2248, the data range has been enlarged by Mars, so you need to cut the useless branches of the searching tree.

An addition chain for n is an integer sequence with the following four properties:

  • a_0 = 1
  • a_m = n
  • a_0 < a_1 < a_2 < ... < a_{m-1} < a_m

For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=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<=n<=10000) . 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.

Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.

样例

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

数据范围与提示

1\le n\le 10^4 ,the task cases will be no more than 10.