← 返回题目列表

Codeforces · 1626/A

A. 等距字母

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$,由小写拉丁字母组成。每个字母在其中出现的次数不超过两次。

您的任务是重新排列字符串中的字母,使得对于恰好出现两次的每对字母,该对字母之间的距离相同。您不得添加或删除字母。

可以证明答案总是存在的。如果有多个答案,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

每个测试用例由一个非空字符串 $$$s$$$ 组成,由小写拉丁字母组成。每个字母在字符串中出现的次数不超过两次。字符串的长度不超过$$$52$$$。

输出

对于每个测试用例,打印一个字符串。每个字母在其中出现的次数应与在字符串 $$$s$$$ 中出现的次数相同。对于每对恰好出现两次的字母,该对字母之间的距离应该相同。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
oelhl
abcdcba
ac

输出 #1

hello
ababcdc
ac

注意

在示例的第一个测试用例中,唯一出现两次的字母是字母“l”。您可以任意重新排列字母,因为没有距离可供比较。

在示例的第二个测试用例中,恰好出现两次的字母是“a”、“b”和“c”。最初,字母“a”之间的距离为$$$6$$$,字母“b”之间的距离为$$$4$$$,字母“c”之间的距离为$$$2$$$。它们不一样,所以我们必须重新排列字母。重新排列后,字母“a”之间的距离为$$$2$$$,字母“b”之间的距离为$$$2$$$,字母“c”之间的距离为$$$2$$$。它们都是一样的,所以答案是有效的。

在示例的第三个测试用例中,没有字母恰好出现两次。因此,任何重新排列都是有效的。包括根本不改变字符串。