E. Минимакс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Префикс-функция от строки $$$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$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Каждый набор входных данных состоит из одной строки $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящей из строчных латинских букв.

Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку $$$t$$$.

Мультимножество букв в строках $$$s$$$ и $$$t$$$ должно совпадать. Значение $$$f(t)$$$, максимума префикс-функции в строке $$$t$$$, должно быть минимальным возможным. Строка $$$t$$$ должна быть лексикографически минимальной среди всех строк, удовлетворяющих предыдущим условиям.

Пример
Входные данные
3
vkcup
abababa
zzzzzz
Выходные данные
ckpuv
aababab
zzzzzz
Примечание

Строка $$$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]$$$.