The factoradic number system is a number system that uses factorials as the place value for each digit. In case you don't know, the factorial value of an integer ~n~ is written ~n!~ and it evaluates to what you get when you multiply together all the integers from ~1~ to ~n~, like this:

$$\displaystyle 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

In the factoradic number system, the rightmost "digit" has a base value of ~0!~, the second digit has a base value of ~1!~, the third digit has a base value of ~2!~ … and the ~n^{th}~ digit has a base value of ~(n-1)!~ Each digit of a factoradic number must be less than or equal to ~n~, where ~n!~ is the place value of the digit.

For example the factoradic number ~3\ 0\ 1\ 0_{!}~ has ~4~ digits. See the table at right for a breakdown of place values and highest digit values. To convert a number from the factoradic number system to base ~10~, you multiply each digit by its base value and sum them all up.

$$\displaystyle 3\ 0\ 1\ 0_{!} = 3 \times 3! + 0 \times 2! + 1 \times 1! + 0 \times 0! = 3 \times 6 + 1 \times 1 = 19$$

Because larger factoradic numbers have digits larger than ~9~, we separate each digit with a space, as shown in the example below:

$$\displaystyle 11\ 9\ 10\ 0\ 8\ 5\ 3\ 2\ 0\ 1\ 1\ 1\ 0_{!}$$

The input will contain ~10~ test cases. Each test case consists of a single line containing a set of non-zero decimal digits concatenated together. The maximum number of digits is ~30~. Each line represents a single factoradic number which is missing all its ~0~s and all the spaces that are supposed to separate the factoradic digits. Find the smallest legal factoradic number that can be made using the decimal digits in their current order. You may add as many zeroes as you wish and place them anywhere you wish.

Output your answer as a factoradic number with each factoradic digit separated by a space.

Sample Input

72
11
12111722
11111722
1566111414121811722

Sample Output

7 0 0 0 0 2 0 0
1 1 0
1 2 1 1 1 7 0 0 0 2 2 0 0
11 1 1 1 7 0 0 0 2 2 0 0
15 6 6 11 14 1 4 12 1 8 1 1 7 0 0 0 2 2 0 0

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org