← 返回题目列表

Codeforces · 1156/B

B. 丑陋的对

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

给您一个由小写拉丁字母组成的字符串。

如果字符串中的一对相邻字母在字母表中也是相邻的,则这些字母被认为是丑陋的。例如,字符串“abaca”在位置 $$$(1, 2)$$$ —“ab”和 $$$(2, 3)$$$ —“ba”处包含丑陋的对。字母“a”和“z”在字母表中不被视为相邻的。

你能重新排列给定字符串的字母,这样就不会有丑陋的字母对吗?您可以选择给定字符串的字母的任意顺序,但不能添加任何新字母或删除现有字母。您也可以保持顺序不变。

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

您还必须回答 $$$T$$$ 单独的查询。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 查询数。

接下来的 $$$T$$$ 行都包含字符串 $$$s$$$ $$$(1 \le |s| \le 100)$$$ — 下一个查询的字符串。保证它只包含小写拉丁字母。

请注意,在 hacks 中你必须设置 $$$T = 1$$$。

输出

打印 $$$T$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 查询的答案。

如果第 $$$i$$$ 查询的答案存在,则打印给定字符串的字母重新排列,使其不包含难看的对。您可以选择给定字符串的字母的任意顺序,但不能添加任何新字母或删除现有字母。您也可以保持顺序不变。

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

否则打印该查询的“无答案”。

示例

输入 #1

4
abcd
gg
codeforces
abaca

输出 #1

cadb
gg
codfoerces
No answer

注意

在第一个示例中,答案“bdac”也是正确的。

第二个示例展示了仅允许字母表中相邻字母的事实。同一个字母就可以了。

第三个示例有很多有效答案。