Restore the Permutation

Joey had saved a permutation of integers from \(1\) to \(n\) in a text file. All the numbers were written as decimal numbers without leading zeros. Then Joe played a practical joke by removing all the spaces from the file. Your task is to restore the original permutation. In other words, given a string \(S\) formed by concatenating the numbers of a permutation of \(1, 2, \ldots, n\) (with no spaces), recover the permutation such that the maximum element is exactly \(n\).

inputFormat

The input consists of a single line containing a string of digits representing the concatenation of the permutation’s elements. There are no spaces or extra characters in the input.

outputFormat

Output the restored permutation with exactly one space between consecutive numbers.

sample

2413

2 4 1 3