Minimax

题意翻译

**本题含有多组数据。** 定义一个函数 $p(s, i)$（其中 $s$ 为一个字符串，$i$ 为一个正整数），它的值为在 $s$ 的子串 $s_1s_2s_3\cdots s_i$ 中，最长的 **既是该子串的真前缀也是该子串的真后缀** 的串的长度。 再定义一函数 $f(s)$，表示 $1 \le i \le |s|, \max(p(s, i))$，即 **$1 \le i \le |s|$ （$|s|$ 表示字符串 $s$ 的长度）中最大的 $p(s, i)$**。 每组数据中，给定一个字符串 $S$，要求任意调整 $S$ 中字符的顺序（可以调顺序，不可以更改字符），使得**调整顺序后的字符串 $S'$ 满足 $f(S')$ 最小**。如果有多个字符串 $S'$ 满足要求，**输出字典序最小的那个**。 所有数据中 $|S|$ 的总和不超过 $10^5$。

题目描述

Prefix function of string $ t = t_1 t_2 \ldots t_n $ and position $ i $ in it is defined as the length $ k $ of the longest proper (not equal to the whole substring) prefix of substring $ t_1 t_2 \ldots t_i $ which is also a suffix of the same substring. For example, for string $ t = $ abacaba the values of the prefix function in positions $ 1, 2, \ldots, 7 $ are equal to $ [0, 0, 1, 0, 1, 2, 3] $ . Let $ f(t) $ be equal to the maximum value of the prefix function of string $ t $ over all its positions. For example, $ f( $ abacaba $ ) = 3 $ . You are given a string $ s $ . Reorder its characters arbitrarily to get a string $ t $ (the number of occurrences of any character in strings $ s $ and $ t $ must be equal). The value of $ f(t) $ must be minimized. Out of all options to minimize $ f(t) $ , choose the one where string $ t $ is the lexicographically smallest.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). Description of the test cases follows. The only line of each test case contains string $ s $ ( $ 1 \le |s| \le 10^5 $ ) consisting of lowercase English letters. It is guaranteed that the sum of lengths of $ s $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print a single string $ t $ . The multisets of letters in strings $ s $ and $ t $ must be equal. The value of $ f(t) $ , the maximum of prefix functions in string $ t $ , must be as small as possible. String $ t $ must be the lexicographically smallest string out of all strings satisfying the previous conditions.

输入输出样例

输入样例 #1

3
vkcup
abababa
zzzzzz

输出样例 #1

ckpuv
aababab
zzzzzz

说明

A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ . In the first test case, $ f(t) = 0 $ and the values of prefix function are $ [0, 0, 0, 0, 0] $ for any permutation of letters. String ckpuv is the lexicographically smallest permutation of letters of string vkcup. In the second test case, $ f(t) = 1 $ and the values of prefix function are $ [0, 1, 0, 1, 0, 1, 0] $ . In the third test case, $ f(t) = 5 $ and the values of prefix function are $ [0, 1, 2, 3, 4, 5] $ .