Префикс-функция от строки \(t = t_1 t_2 \ldots t_n\) и позиции \(i\) в ней — это длина \(k\) наибольшего собственного (не равного всей подстроке) префикса подстроки \(t_1 t_2 \ldots t_i\), который одновременно является суффиксом этой подстроки.
Например, для строки \(t = \) abacaba значения префикс-функции от позиций \(1, 2, \ldots, 7\) равны \([0, 0, 1, 0, 1, 2, 3]\).
Введём функцию \(f(t)\), равную максимальному значению префикс-функции строки \(t\) по всем её позициям. Например, \(f(\)abacaba\() = 3\).
Вам дана строка \(s\). Переставьте её символы произвольным образом, чтобы получить строку \(t\) (количество вхождений любого символа в строки \(s\) и \(t\) должно совпадать). Значение \(f(t)\) должно быть минимальным возможным. Среди всех вариантов минимизировать \(f(t)\) выберите тот, где строка \(t\) лексикографически минимальна.
Выходные данные
Для каждого набора входных данных выведите одну строку \(t\).
Мультимножество букв в строках \(s\) и \(t\) должно совпадать. Значение \(f(t)\), максимума префикс-функции в строке \(t\), должно быть минимальным возможным. Строка \(t\) должна быть лексикографически минимальной среди всех строк, удовлетворяющих предыдущим условиям.
Примечание
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
В первом наборе входных данных \(f(t) = 0\) и значения префикс-функции равны \([0, 0, 0, 0, 0]\) для любой перестановки букв. Строка ckpuv является лексикографически минимальной перестановкой букв строки vkcup.
Во втором наборе входных данных \(f(t) = 1\), значения префикс-функции равны \([0, 1, 0, 1, 0, 1, 0]\).
В третьем наборе входных данных \(f(t) = 5\), значения префикс-функции равны \([0, 1, 2, 3, 4, 5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
vkcup
abababa
zzzzzz
|
ckpuv
aababab
zzzzzz
|