Вам дана строка \(s\). Вы можете поменять порядок символов и получить строку \(t\). Определим \(t_{\mathrm{max}}\) как лексикографический максимум строки \(t\) и перевернутой строки \(t\).
По данной строке \(s\) определите лексикографически минимальное значение \(t_{\mathrm{max}}\) по всем перестановкам \(t\) строки \(s\).
Строка \(a\) лексикографически меньше строки \(b\) тогда и только тогда, когда одно из двух условий выполнено:
- \(a\) является префиксом \(b\), но \(a \ne b\);
- в первой позиции, в которой \(a\) и \(b\) отличаются, в строке \(a\) стоит символ, который встречается в алфавите раньше, чем соответствующий символ в строке \(b\).
Выходные данные
Для каждого набора входных данных выведите лексикографически минимальное значение строки \(t_{\mathrm{max}}\) по всем перестановкам \(t\) строки \(s\).
Примечание
В первом наборе входных данных есть одна перестановка символов строки \(s\), это «a».
Во втором наборе входных данных есть три возможных перестановки символов \(s\):
- \(t = \mathtt{aab}\): \(t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}\)
- \(t = \mathtt{aba}\): \(t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}\)
- \(t = \mathtt{baa}\): \(t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}\)
Лексикографически минимальное значение \(t_{\mathrm{max}}\) по всем случаям это «aba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|