Begin a sequence of distinct natural numbers Ni, i = 0, 1, 2,... , with the number B (= N0) ; generate numbers Ni, i = 1, 2,... , recursively and end the sequence with the last generated number E. The characteristic of numbers and the process for generation are stated below:

* Each number in the sequence contains an even number of decimal digits and is of the form f1d1f2d2fk...dk where d1, d2,..., dk, are k distinct digits in increasing order and each fj is a non-zero digit.

* For i = 0, 1, 2,... , if Ni = f1d1f2d2...fkdk then Ni+1 = F1D1F2D2...FKDK , where K >= k ; D1, D2,..., DK , are distinct digits that occur in Ni and appear in increasing order in Ni+1 ; and FJ is the frequency of DJ in Ni , for J = 1, 2,..., K . For example if Ni = 102335 then Ni+1 = 1011122315.

Write a program to find for a given E, the longest sequence of numbers that ends with E and begins with the smallest B.

Again consider an example; if E =1011122315 then the required sequence of numbers is 303355 103325 1011122315.

Input

The input may contain multiple test cases.

Each test case contains only one input, viz., E.

The input terminates when a line containing 0 appears as a test case.

Output

For each test case, print the longest sequence of numbers that ends with E and begins with the smallest B. Use space to separate two consecutive numbers in the sequence.

Example

Sample Input
1011122315
22
112213
0
Sample Output
303355 103325 1011122315
22
13 1113 3113 2123 112213