题目描述

你有幸得知世间所有重要问题的答案，这一次，答案是仅由小写英文字母构成的字符串 $s$。你想要把这个字符串隐藏起来。

你另有一个同样只由小写英文字母组成的字符串 $t$。你需要重排 $t$ 的全部字符，使得重排后的字符串中，$s$ 至少作为一个子序列出现一次。在所有满足条件的重排结果中，找出字典序最小的那一个。

$^{\text{※}}$序列 $a$ 是 $b$ 的子序列的含义：可以从 $b$ 中删除若干个（可以删 0 个或者全部）任意位置的字符得到 $a$。

$^{\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$ 是其子序列的字典序最小字符串。如果不存在合法重排，输出 Impossible。

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$ 的字符串。

原题链接

原题链接