## BEGIN - Begin

no tags

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\$ \ge\$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
```

 Added by: Duc Date: 2008-12-09 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: ACM Kanpur 2006