CF1281B.Azamon Web Services

Your friend Jeff Zebos has been trying to run his new online company, but it's not going very well. He's not getting a lot of sales on his website which he decided to call Azamon. His big problem, you think, is that he's not ranking high enough on the search engines. If only he could rename his products to have better names than his competitors, then he'll be at the top of the search results and will be a millionaire.

After doing some research, you find out that search engines only sort their results lexicographically. If your friend could rename his products to lexicographically smaller strings than his competitor's, then he'll be at the top of the rankings!

To make your strategy less obvious to his competitors, you decide to swap no more than two letters of the product names.

Please help Jeff to find improved names for his products that are lexicographically smaller than his competitor's!

Given the string $s$ representing Jeff's product name and the string $c$ representing his competitor's product name, find a way to swap at most one pair of characters in $s$ (that is, find two distinct indices $i$ and $j$ and swap $s_i$ and $s_j$) such that the resulting new name becomes strictly lexicographically smaller than $c$, or determine that it is impossible.

Note: String $a$ is strictly lexicographically smaller than string $b$ if and only if one of the following holds:

• $a$ is a proper prefix of $b$, that is, $a$ is a prefix of $b$ such that $a \neq b$;
• There exists an integer $1 \le i \le \min{(|a|, |b|)}$ such that $a_i \lt b_i$ and $a_j = b_j$ for $1 \le j \lt i$.

你的朋友杰夫·泽博斯（Jeff Zebos）一直在努力经营他的新在线公司，但经营状况并不理想。他的网站（他将其命名为 Azamon）销量不佳。你认为，他面临的主要问题是搜索引擎排名不够高。只要他能将产品名称改得比竞争对手更“好”，他就能够位居搜索结果榜首，从而成为百万富翁。

经过一番调研，你发现搜索引擎仅按字典序对结果进行排序。如果你的朋友能将产品名称改为字典序严格小于竞争对手名称的字符串，那么他就能跃居搜索结果榜首！

为使该策略对竞争对手而言不那么明显，你决定最多交换产品名称中的两个字母。

请帮助杰夫为其产品寻找改进后的名称，使其字典序严格小于竞争对手的产品名称！

给定字符串 $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 \lt b_i$，且对所有 $1 \le j \lt i$ 均有 $a_j = b_j$。

The first line of input contains a single integer $t$ ($1 \le t \le 1500$) denoting the number of test cases. The next lines contain descriptions of the test cases.

Each test case consists of a single line containing two space-separated strings $s$ and $c$ ($2 \le |s| \le 5000, 1 \le |c| \le 5000$). The strings $s$ and $c$ consists of uppercase English letters.

It is guaranteed that the sum of $|s|$ in the input is at most $5000$ and the sum of the $|c|$ in the input is at most $5000$.

输入的第一行包含一个整数 $t$（$1 \le t \le 1500$），表示测试用例的数量。接下来的行包含各测试用例的描述。

每个测试用例由一行组成，包含两个以空格分隔的字符串 $s$ 和 $c$（$2 \le |s| \le 5000$，$1 \le |c| \le 5000$）。字符串 $s$ 和 $c$ 仅由大写英文字母组成。

保证输入中所有 $|s|$ 的总和不超过 $5000$，且所有 $|c|$ 的总和也不超过 $5000$。

For each test case, output a single line containing a single string, which is either

• the new name which is obtained after swapping no more than one pair of characters that is strictly lexicographically smaller than $c$. In case there are many possible such strings, you can output any of them;
• three dashes (the string "---" without quotes) if it is impossible.

对于每个测试用例，输出一行，包含一个字符串，该字符串为：

• 通过交换至多一对字符后得到的新名字，且该新名字严格字典序小于 $c$。若存在多个满足条件的字符串，可输出其中任意一个；
• 若不存在满足条件的字符串，则输出三个短横线（即字符串 "---"，不带引号）。

In the first test case, it is possible to swap the second and the fourth letters of the string and the resulting string "AMAZON" is lexicographically smaller than "APPLE".

It is impossible to improve the product's name in the second test case and satisfy all conditions.

In the third test case, it is possible not to swap a pair of characters. The name "APPLE" is lexicographically smaller than "BANANA". Note that there are other valid answers, e.g., "APPEL".

在第一个测试用例中，可以交换字符串的第二个和第四个字母，得到的结果字符串 “AMAZON” 在字典序上小于 “APPLE”。

在第二个测试用例中，无法在满足所有条件的前提下改进产品的名称。

在第三个测试用例中，可以不交换任何一对字符。名称 “APPLE” 在字典序上小于 “BANANA”。注意，存在其他合法的答案，例如 “APPEL”。