Вам дана строка \(s\). Вы можете поменять порядок символов и получить строку \(t\). Определим \(t_{\mathrm{max}}\) как лексикографический максимум строки \(t\) и перевернутой строки \(t\).
По данной строке \(s\) определите лексикографически минимальное значение \(t_{\mathrm{max}}\) по всем перестановкам \(t\) строки \(s\).
Строка \(a\) лексикографически меньше строки \(b\) тогда и только тогда, когда одно из двух условий выполнено:
В первой строке находится единственное целое число \(t\) (\(1 \leq t \leq 10^5\))— количество наборов входных данных. Описания наборов входных данных следуют.
В единственной строке для каждого набора входных данных находится строка \(s\) (\(1 \leq |s| \leq 10^5\)). \(s\) состоит из строчных символов латинского алфавита.
Гарантируется, что сумма \(|s|\) по всем наборам входных данных не превосходит \(10^5\).
Для каждого набора входных данных выведите лексикографически минимальное значение строки \(t_{\mathrm{max}}\) по всем перестановкам \(t\) строки \(s\).
В первом наборе входных данных есть одна перестановка символов строки \(s\), это «a».
Во втором наборе входных данных есть три возможных перестановки символов \(s\):
Лексикографически минимальное значение \(t_{\mathrm{max}}\) по всем случаям это «aba».
12 a aab abb abc aabb aabbb aaabb abbb abbbb abbcc eaga ffcaba
a aba bab bca abba abbba ababa bbab bbabb bbcca agea acffba
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач