MERN E-commerce: Optimize Box IDs

Amazon MERN #5 is an interleaved algorithm problem that is already included in the main algorithm library; it is the same problem as Amazon #34 "Get Minimum String (Box Lex-Smallest)". The Amazon #13 that the #5 page points to is actually a different interval-counting problem, so this entry is mapped to #34 by its title and problem meaning.

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

This site's standard I/O, examples, and judging reuse the verified Amazon #34 and do not redefine the operation.

输入格式

A single 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

样例说明

This problem is the same as Amazon #34 and reuses its verified examples, reference implementation, and tests; the original #5 link to Amazon #13 is unrelated to this problem.