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