This page is still under construction.

Parts of this page are still being built. What you see may change.

Addition Chains

Time limit1sMemory limit256 MB

Summary
For each n up to 100, find a shortest addition chain ending at n and print the lexicographically smallest among all shortest ones.
Level

Hard8 of 10

Topics
DFS, Backtracking, Brute force, Greedy
Solved
No attempts yet

Problem

For a natural number nn, a sequence of natural numbers ⟨a0,a1,…,am⟩\langle a_0, a_1, \ldots, a_m \rangle is called an addition chain for nn if it satisfies all four of the following conditions.

  1. a0=1a_0 = 1
  2. am=na_m = n
  3. a0<a1<a2<⋯<am−1<ama_0 < a_1 < a_2 < \cdots < a_{m-1} < a_m
  4. For every k (1≤k≤m)k\ (1 \le k \le m) there exist two indices i,ji, j with 0≤i,j≤k−10 \le i, j \le k-1 (they may be equal) such that ak=ai+aja_k = a_i + a_j.

In other words, the first term is 11, the last term is nn, the sequence is strictly increasing, and every term is the sum of two earlier terms (the same term may be used twice). An addition chain with the fewest terms (that is, the smallest mm) is called a shortest addition chain.

There can be several shortest addition chains. Among them, output the one that is lexicographically smallest. To compare two sequences lexicographically, compare their terms one by one from the front; at the first position where they differ, the sequence with the smaller value comes first.

Given several natural numbers nn, write a program that, for each of them, finds the lexicographically smallest shortest addition chain.

Input

The input consists of one or more test cases. Each test case is a single line containing a natural number nn (1≤n≤1001 \le n \le 100). The last line of the input contains a single 00, which is not processed.

Output

For each test case, print on one line the lexicographically smallest shortest addition chain, with the terms separated by single spaces.

Examples2

  1. Example 1

    Input
    5
7
12
15
77
0
    Expected output
    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

  2. Example 2

    Input
    1
2
3
4
5
6
7
8
9
10
0
    Expected output
    1
1 2
1 2 3
1 2 4
1 2 3 5
1 2 3 6
1 2 3 4 7
1 2 4 8
1 2 3 6 9
1 2 3 5 10