Get Minimum String (Box Lex-Smallest)

One operation takes out any digit d, changes it to min(d+1,9), and inserts it at any position. You may perform any number of operations (including 0). Find the lexicographically smallest final string, keeping leading zeros.

输入格式

One line containing a digit string of length 1..200000.

输出格式

Output the lexicographically smallest digit string, keeping leading zeros.

样例 1

输入：

26547

输出：

24677

样例 2

输入：

0

输出：

0

样例 3

输入：

21

输出：

13

样例说明

Example 1: 6 and 5 have a smaller 4 to their right, so they are moved and become 7 and 6; sorting them together with the kept 2, 4 and 7 gives 24677. Example 2: doing nothing is already the smallest, so the output is 0. Example 3: take 2 out, turning it into 3, and insert it after 1 to get 13.