У 378QAQ есть строка \(s\) длины \(n\). Определим ядро строки как подстроку\(^\dagger\) с максимальным лексикографическим\(^\ddagger\) порядком.
Например, ядром «\(\mathtt{bazoka}\)» является «\(\mathtt{zoka}\)», а ядром «\(\mathtt{aaa}\)» является «\(\mathtt{aaa}\)».
378QAQ хочет переставить символы в строке \(s\) так, чтобы ядро было лексикографически минимальным. Найдите лексикографически минимальное возможное ядро среди всех перестановок \(s\).
\(^\dagger\) Подстрока строки \(s\) — это непрерывный отрезок букв из \(s\). Например, «\(\mathtt{defor}\)», «\(\mathtt{code}\)» и «\(\mathtt{o}\)» являются подстроками «\(\mathtt{codeforces}\)», а «\(\mathtt{codes}\)» и «\(\mathtt{aaa}\)» не являются.
\(^\ddagger\) Строка \(p\) лексикографически меньше строки \(q\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(p\) является префиксом \(q\), но \(p \ne q\); или
- в первой позиции, где \(p\) и \(q\) отличаются, строка \(p\) имеет меньший символ, чем символ на соответствующей поозиции в \(q\) (при сравнении по их ASCII-коду).
Например, «\(\mathtt{code}\)» и «\(\mathtt{coda}\)» лексикографически меньше, чем «\(\mathtt{codeforces}\)», а «\(\mathtt{codeforceston}\)» и «\(\mathtt{z}\)» — нет.
Примечание
В первом наборе входных данных все возможные перестановки и соответствующие им ядра выглядят следующим образом:
- «\(\mathtt{qaq}\)», его ядро — «\(\mathtt{qaq}\)».
- «\(\mathtt{aqq}\)», его ядро — «\(\mathtt{qq}\)».
- «\(\mathtt{qqa}\)», его ядро — «\(\mathtt{qqa}\)».
Таким образом, ядро с минимальным лексикографическим порядком среди всех перестановок — это «\(\mathtt{qaq}\)».