Дана строка \(s\). Можно ровно один раз применить к строке такую операцию: выбрать индекс \(i\) и переставить символ \(s_i\) в начало строки (удалив его на старой позиции). Например, если к строке «abaacd» применить операцию с индексом \(i=4\) в нумерации с \(1\), то получится строка «aabacd». Какую лексикографически минимальную\(^{\dagger}\) строку можно получить одной такой операцией?
\(^{\dagger}\)Строка \(a\) лексикографически меньше строки \(b\) такой же длины, если и только если выполняется следующее:
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите лексикографически минимальную строку, которую можно получить после применения одной операции из условия к исходной строке ровно один раз.
Примечание
В первом наборе нужно переместить последний символ в начало.
Во втором наборе входных данных нужно перенести в начало вторую букву «a».
В третьем наборе нужно применить операцию с \(i=1\), тогда строка не изменится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
cba
4
acac
5
abbcb
4
aaba
|
acb
aacc
abbcb
aaab
|