← 返回题目列表

Codeforces · 2174/A

A. 大海捞针

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

你很幸运知道世界上所有重要问题的答案。这次,答案是字符串 $$$s$$$,仅由小写英文字母组成。你想隐藏这个字符串。

您还有另一个字符串 $$$t$$$ 也仅由小写英文字母组成。您需要打乱 $$$t$$$ 中的字母,以便字符串 $$$s$$$ 作为子序列 $$$^{\text{*}}$$$ 在 $$$t$$$ 中至少出现一次。在包含 $$$s$$$ 作为子序列的 $$$t$$$ 的所有可能重新排序中,找到字典顺序最小的 $$$^{\text{†}}$$$ 之一。

$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。

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

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

输入

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

每个测试用例的第一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 10^5$$$),其中 $$$|s|$$$ 是字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含字符串 $$$t$$$ ($$$|s| \le |t| \le 10^5$$$)。

两个字符串均仅包含小写英文字母。

所有测试用例的 $$$|t|$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印单个字符串:字符串 $$$t$$$ 中字母的字典顺序最小重新排序,其中包含 $$$s$$$ 作为子序列。如果不存在这样的字符串,则打印“不可能“改为。

示例

输入
复制

3
dcbe
bedbaecfc
babadab
abacabadabacaba
babaisyou
flagiswin

输出
复制

abcdcbeef
aaaaabababccdab
Impossible

注意

在第一个测试用例中,$$$\mathtt{abc}\,\mathtt{dcbe}\,\mathtt{ef}$$$ 包含 $$$\mathtt{dcbe}$$$。

在第二个测试用例中,$$$\mathtt{aaaaa}\,\mathtt{baba}\,\mathtt{bcc}\,\mathtt{dab}$$$ 还包含 $$$\mathtt{babadab}$$$。

可以证明这些是满足给定条件的字典顺序最小的字符串。

在第三个测试用例中,$$$t$$$ 中的字母重新排列不包含 $$$s$$$。