AT_arc209_b.[ARC209B] Minimize Even Palindrome

对于一个仅由小写英文字母组成的字符串 $s$，令 $f(s)$ 表示 $s$ 中长度为偶数的回文子串的数目。更具体地说，$f(s)$ 是满足以下所有条件的整数对 $l, r$ 的数量：

• $1 \leq l \leq r \leq |s|$。
• $r - l + 1$ 是偶数。
• $s_l s_{l+1} \cdots s_{r}$ 是回文串。

给定一个仅由小写英文字母组成的字符串 $S$，输出一个通过重新排列 $S$ 中字符得到的字符串 $S'$，使得 $f(S')$ 最小。

你将会得到 $T$ 组测试数据。请分别求解。

输入从标准输入读取，格式如下：

$T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$

每组测试数据格式如下：

$S$

输出共 $T$ 行。

第 $i$ 行输出一行字符串，为通过重新排列 $S$ 得到的某一个 $S'$，使得 $f(S')$ 最小。如果有多个满足要求的 $S'$，输出其中任意一个均可。

样例解释 1

对于第一组测试数据，$S$ 的所有排列结果为 see、ese、ees。其中，只有 ese 能使 $f(S’)$ 最小，因此输出它。

对于第二组测试数据，例如输出 xxyxxx 也是符合条件的。

约束条件

• $1 \leq T \leq 10^5$
• $2 \leq |S| \leq 2 \times 10^5$
• $S$ 仅包含小写英文字母。
• 所有测试数据中 $|S|$ 的和不超过 $2 \times 10^5$。

由 ChatGPT 5 翻译