Permutation with no spaces

Interview

Time limit1sMemory limit256 MB

Summary

Recover the permutation from 1 to N whose decimal forms concatenate to the given digit string, choosing the lexicographically smallest one on ties.

Level: Medium5 of 10
Topics: Backtracking, Brute force, String
Solved: No attempts yet

Problem

A permutation that uses each of the numbers $1$ through $N$ once was written in decimal on one line, with a single space between neighboring numbers, and saved to a file. Someone then deleted every space in that file, so all that is left is one long run of digits.

Put the spaces back and recover the permutation.

Input

The first line contains the digit string that remains after every space was deleted.

The string is a permutation of the numbers $1$ through $N$ concatenated from front to back, where $1 \le N \le 50$ . The value of $N$ is not given. The string can always be split back into such a permutation.

Output

Print the recovered permutation on one line, with a single space between neighboring numbers. Do not forget the spaces.

When more than one permutation fits the string, compare two candidates number by number from the front and print the one whose number is smaller at the first position where they differ. That is, print the lexicographically smallest of the valid permutations.

Examples3

Example 1
Input
```
4111109876532
```
Expected output
```
4 1 11 10 9 8 7 6 5 3 2
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
12345678910
```
Expected output
```
1 2 3 4 5 6 7 8 9 10
```