← 返回题目列表

Codeforces · 1602/A

A. 两个子序列

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

给你一个字符串 $$$s$$$。您需要找到两个非空字符串 $$$a$$$ 和 $$$b$$$ 以满足以下条件:

1. 字符串$$$a$$$ 和$$$b$$$ 都是$$$s$$$ 的子序列。
2. 对于每个索引 $$$i$$$,字符串 $$$s$$$ 的字符 $$$s_i$$$ 必须恰好属于字符串 $$$a$$$ 或 $$$b$$$ 之一。
3. 字符串 $$$a$$$ 按字典顺序是最小可能的;字符串 $$$b$$$ 可以是任何可能的字符串。

给定字符串 $$$s$$$,打印任何有效的 $$$a$$$ 和 $$$b$$$。

提醒:

如果可以通过删除几个(可能是零)元素从 $$$s$$$ 获得 $$$a$$$ ($$$b$$$),则字符串 $$$a$$$ ($$$b$$$) 是字符串 $$$s$$$ 的子序列。例如,“dores”、“cf”和“for”是“codeforces”的子序列,而“decor”和“fork”则不是。

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

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

输入

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

每个测试用例的第一行也是唯一一行包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 100$$$ 其中 $$$|s|$$$ 表示 $$$s$$$ 的长度)。字符串 $$$s$$$ 由小写拉丁字母组成。

输出

对于每个测试用例,打印满足给定条件的字符串 $$$a$$$ 和 $$$b$$$。如果有多个答案,请打印其中一个。

示例

输入 #1

3
fc
aaaa
thebrightboiler

输出 #1

c f
a aaa
b therightboiler

注意

在第一个测试用例中,只有两个选择:$$$a =$$$ f 和 $$$b = $$$ c 或 $$$a = $$$ c 和 $$$b = $$$ f。并且 $$$a = $$$c 按字典顺序小于 $$$a = $$$ f。

在第二个测试用例中,a 是字符串中唯一的字符。

在第三个测试用例中,可以证明b是$$$s$$$的字典顺序最小的子序列。第二个字符串可以有两种变体;这里给出了其中之一。