### Addition Chains

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

An addition chain for *n* is an integer sequence *<a _{0}, a_{1},a_{2},...,a_{m}>* with the following four properties:

*a*= 1_{0}*a*=_{m}*n**a*_{0}<a_{1}<a_{2}<...< a_{m-1}<a_{m}- For each
*k*(1<=*k*<=*m*) there exist two (not neccessarily different) integers*i*and*j*(0<=*i*,*j*<=*k*-1) with*a*_{k}=a_{i}+a_{j}

*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.

#### Input

The input file will contain one or more test cases. Each test case consists of one line containing one integer

*n*(1<=*n*<=100). Input is terminated by a value of zero (0) for*n*.#### Output

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.

#### Sample Input

5 7 12 15 77 0

#### Sample 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

#### Hint

#### Source

1996/97 ACM International Collegiate Programming Contest (University of Ulm Internal Contest)