← 返回题目列表

Codeforces · 1480/A

A. 又一个弦乐游戏

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

Homer 有两个朋友 Alice 和 Bob。两人都是弦乐迷。

有一天,Alice 和 Bob 决定玩一个游戏,字符串 $$$s = s_1 s_2 \dots s_n$$$,长度为 $$$n$$$,由小写英文字母组成。他们轮流移动,爱丽丝率先移动。

在一步棋中,玩家必须选择一个之前没有选择过的索引 $$$i$$$ ($$$1 \leq i \leq n$$$),并将 $$$s_i$$$ 更改为 $$$c \neq s_i$$$ 中的任何其他小写英文字母 $$$c$$$。

当所有索引都被选择后,游戏结束。

Alice的目标是使最终字符串按字典顺序尽可能小,而Bob的目标是使最终字符串按字典顺序尽可能大。两人都是游戏高手,所以总是能以最佳状态玩游戏。荷马不是游戏专家,所以他想知道最后的字符串会是什么。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。

输入

每个测试包含多个测试用例。第一行包含 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1 \leq |s| \leq 50$$$)。

输出

对于每个测试用例,在一行中打印最终字符串。

示例

输入 #1

3
a
bbbb
az

输出 #1

b
azaz
by

注意

在第一个测试用例中:Alice 迈出第一步,必须将唯一的字母更改为不同的字母,因此她将其更改为“b”。

在第二个测试用例中:Alice 将第一个字母更改为“a”,然后 Bob 将第二个字母更改为“z”,Alice 将第三个字母更改为“a”,然后 Bob 将第四个字母更改为“z”。

在第三个测试用例中:Alice 将第一个字母更改为“b”,然后 Bob 将第二个字母更改为“y”。