У вас есть строка \(s\), состоящая из цифр от \(0\) до \(9\) включительно. Вы можете произвести над ней следующую операцию любое (возможно нулевое) количество раз:
- Вы можете выбрать позицию \(i\) и удалить цифру \(d\) на \(i\)-й позиции. Затем нужно вставить цифру \(\min{(d + 1, 9)}\) в любую позицию (в начало, в конец или между любыми двумя соседними цифрами).
Какую лексикографически минимальную строку вы можете получить после этих операций?
Строка \(a\) лексикографически меньше строки \(b\) той же длины, если и только если выполняется следующее:
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится цифра меньшая, чем соответствующая цифра в \(b\).
Выходные данные
Выведите единственную строку — лексикографически минимальную строку, которую можно получить.
Примечание
В первом наборе входных данных:
- Удалим \(8\) и поместим в конец строки \(9\). Получается строка \(04299\).
- Удалим \(4\) и поместим на \(3\)-ю позицию строки \(5\). Получается строка \(02599\).
Во втором и третьем наборах входных данных не нужно ничего делать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
04829
9
01
314752277691991
|
02599
9
01
111334567888999
|