Дана строка \(s\), состоящая из цифр от \(0\) до \(9\). За одно действие можно выбрать любую цифру, кроме \(0\) или самой левой цифры, уменьшить её на \(1\) и поменять с цифрой слева от неё местами.
Например, за одну операцию из строки \(1023\) можно получить строки \(1103\), \(1022\).
Найдите, какую лексикографически максимальную строку можно получить с помощью этой операции.
Выходные данные
Для каждого набора входных данных выведите ответ в единственной строке.
Примечание
В первом примере подойдёт следующая последовательность операций: \(19 \rightarrow 81\).
Во втором примере подойдёт следующая последовательность операций: \(1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710\).
В четвёртом примере подойдёт следующая последовательность операций: \(51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
19
1709
11555
51476
9876543210
5891917899
|
81
6710
33311
55431
9876543210
7875567711
|