← 返回题目列表

Codeforces · 1617/A

A. 禁止的子序列

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

给定字符串 $$$S$$$ 和 $$$T$$$,由小写英文字母组成。保证 $$$T$$$ 是字符串 abc 的排列。

查找字符串 $$$S'$$$,即 $$$S$$$ 按字典顺序排列的最小排列,使得 $$$T$$$ 不是 $$$S'$$$ 的子序列。

如果每个不同字符在两个字符串中出现的次数相同,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的排列。

如果可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。

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

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

输入

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

每个测试用例的第一行包含一个字符串 $$$S$$$ ($$$1 \le |S| \le 100$$$),由小写英文字母组成。

每个测试用例的第二行包含一个字符串 $$$T$$$,它是字符串 abc 的排列。 (因此,$$$|T| = 3$$$)。

请注意,所有测试用例中 $$$|S|$$$ 的总和没有限制。

输出

对于每个测试用例,输出单个字符串 $$$S'$$$,即 $$$S$$$ 按字典顺序排列的最小排列,使得 $$$T$$$ 不是 $$$S'$$$ 的子序列。

示例

输入 #1

7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc

输出 #1

aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac

注意

在第一个测试用例中,aaaabbc 和 aaaabcb 按字典顺序都小于 aaaacbb,但它们包含 abc 作为子序列。

在第二个测试用例中,abccc 是 cccba 的最小排列,并且不包含 acb 作为子序列。

在第三个测试用例中,bcdis 是 dbsic 的最小排列,并且不包含 bac 作为子序列。