你的朋友 Jeff Zebos 一直在尝试经营他的新在线公司,但进展并不顺利。他在自己的网站上没有获得太多销量,他决定将其命名为 Azamon。你认为他的大问题是他在搜索引擎上的排名不够高。如果他能够将自己的产品重新命名为比竞争对手更好的名字,那么他就会出现在搜索结果的顶部,并且成为百万富翁。
经过一些研究,您发现搜索引擎仅按字典顺序对结果进行排序。如果您的朋友可以将他的产品重命名为比竞争对手更小的字典顺序字符串,那么他将名列前茅!
为了让您的策略对其竞争对手不那么明显,您决定交换不超过两个产品名称字母。
请帮助 Jeff 为他的产品找到改进的名称,这些名称按字典顺序小于竞争对手的名称!
给定表示 Jeff 产品名称的字符串 $$$s$$$ 和表示竞争对手产品名称的字符串 $$$c$$$,找到一种方法交换 $$$s$$$ 中最多一对字符(即找到两个不同的索引 $$$i$$$ 和 $$$j$$$ 并交换 $$$s_i$$$ 和 $$$s_j$$$),使得生成的新名称严格成为按字典顺序小于 $$$c$$$,或者确定这是不可能的。
注意:当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序严格小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的正确前缀,即 $$$a$$$ 是 $$$b$$$ 的前缀,使得 $$$a \neq b$$$;
- 存在一个整数 $$$1 \le i \le \min{(|a|, |b|)}$$$,使得 $$$a_i < b_i$$$ 且 $$$a_j = b_j$$$ 对于 $$$1 \le j < i$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1500$$$) 表示测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例由一行组成,其中包含两个空格分隔的字符串 $$$s$$$ 和 $$$c$$$ ($$$2 \le |s| \le 5000, 1 \le |c| \le 5000$$$)。字符串$$$s$$$ 和$$$c$$$ 由大写英文字母组成。
保证输入中的 $$$|s|$$$ 之和最多为 $$$5000$$$,输入中的 $$$|c|$$$ 之和最多为 $$$5000$$$。
输出
对于每个测试用例,输出包含单个字符串的单行,该字符串是
- 交换不超过一对严格字典顺序小于 $$$c$$$ 的字符后获得的新名称。如果有很多可能的此类字符串,则可以输出其中任何一个;
- 如果不可能,则三个破折号(字符串“---”不带引号)。
示例
输入 #1
3 AZAMON APPLE AZAMON AAAAAAAAAAALIBABA APPLE BANANA
输出 #1
AMAZON --- APPLE
注意
在第一个测试用例中,可以交换字符串的第二个和第四个字母,结果字符串“AMAZON”按字典顺序小于“APPLE”。
不可能在第二个测试用例中改进产品名称并满足所有条件。
在第三个测试用例中,可以不交换一对字符。按字典顺序,名称“APPLE”比“BANANA”小。请注意,还有其他有效答案,例如“APPEL”。