Forbidden Subsequence

题意翻译

给定两个仅包含小写字母的字符串 $S$ 和 $T$，保证 $T$ 仅包含 `a`、`b`、`c` 且这三个小写字母都出现且仅出现一次。现重新排列字符串 $S$，记重新排列之后的字符串为 $S'$，我们希望 $T$ 不是 $S'$ 的子序列。请你求出重新排列之后满足该要求的字符串 $S'$，如果满足要求的 $S'$ 有多个，输出字典序最小的那一个。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^3$。 - $1\leqslant |S|\leqslant 100$，$|T|=3$。 Translated by Eason_AC 2021.12.17

题目描述

You are given strings $ S $ and $ T $ , consisting of lowercase English letters. It is guaranteed that $ T $ is a permutation of the string abc. Find string $ S' $ , the lexicographically smallest permutation of $ S $ such that $ T $ is not a subsequence of $ S' $ . String $ a $ is a permutation of string $ b $ if the number of occurrences of each distinct character is the same in both strings. A string $ a $ is a subsequence of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements. A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a string $ S $ ( $ 1 \le |S| \le 100 $ ), consisting of lowercase English letters. The second line of each test case contains a string $ T $ that is a permutation of the string abc. (Hence, $ |T| = 3 $ ). Note that there is no limit on the sum of $ |S| $ across all test cases.

输出格式

For each test case, output a single string $ S' $ , the lexicographically smallest permutation of $ S $ such that $ T $ is not a subsequence of $ 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

说明

In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence. In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence. In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.