CF1526D Kill Anton

在拒绝了 $10^{100}$ 个数据结构题目后，Errorgorn 对 Anton 非常生气，决定杀死他。 Anton 的 DNA 可以表示为一个只包含字符 "ANTON" 的字符串 $a$（实际上只有 $4$ 种不同的字符）。 Errorgorn 可以将 Anton 的 DNA 改变为字符串 $b$，其中 $b$ 必须是 $a$ 的一个排列。然而，Anton 的身体可以抵御这种攻击。在 $1$ 秒内，他的身体可以交换 DNA 中相邻的两个字符，将其逐步变回 $a$。Anton 的身体很聪明，会用最少的操作次数。 为了最大化 Anton 死亡的概率，Errorgorn 想要将 Anton 的 DNA 变成一个使 Anton 的身体恢复 DNA 所需时间最长的字符串。但由于 Errorgorn 忙于出更多的数据结构题，他需要你的帮助来找到最优的字符串 $b$。你能帮他吗？

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 100000)$，表示测试用例的数量。 每个测试用例的第一行包含一个字符串 $a$（$1 \leq |a| \leq 100000$）。$a$ 只包含字符 "A"、"N"、"O" 和 "T"。 保证所有测试用例中 $|a|$ 的总和不超过 $100000$。

对于每个测试用例，输出一个字符串 $b$。如果有多种答案，可以输出任意一种。$b$ 必须是字符串 $a$ 的一个排列。

对于第一个测试用例，将 NNOTA 变回 ANTON 需要 $7$ 秒： NNOTA $\to$ NNOAT $\to$ NNAOT $\to$ NANOT $\to$ NANTO $\to$ ANNTO $\to$ ANTNO $\to$ ANTON。 注意，你不能输出如 AANTON、ANTONTRYGUB、AAAAA 和 anton 这样的字符串，因为它们不是 ANTON 的排列。 对于第二个测试用例，将 AANN 变回 NAAN 需要 $2$ 秒。注意，其他如 NNAA 和 ANNA 也可以被接受。 由 ChatGPT 4.1 翻译