CF2174A.Needle in a Haystack

You got lucky to know the answer to all important questions in the world. This time, the answer is the string $s$, consisting of lowercase English letters only. You want to hide this string.

You have another string $t$ also consisting of lowercase English letters only. You need to shuffle the letters in $t$ so that the string $s$ appears at least once in $t$ as a subsequence$^{\text{∗}}$. Among all possible reorderings of $t$ containing $s$ as a subsequence, find the lexicographically smallest$^{\text{†}}$ one.

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

$^{\text{†}}$A string $a$ is lexicographically smaller than string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$; or
• 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$.

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

你还有另一个字符串 $t$，它也仅由小写英文字母组成。你需要对 $t$ 中的字母进行重排，使得字符串 $s$ 至少作为 $t$ 的一个子序列$^{\text{∗}}$ 出现。在所有满足“$s$ 是其子序列”的 $t$ 的重排中，请找出字典序最小$^{\text{†}}$ 的那个。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可通过从 $b$ 中任意位置删除若干（可能为零个或全部）元素而得到。

$^{\text{†}}$ 字符串 $a$ 的字典序小于字符串 $b$，当且仅当以下条件之一成立：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀，但 $a \ne b$）；或者
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $b$ 中对应位置的字母。

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10^4$). The description of the test cases follows.

The first line of each test case contains the string $s$ ($1 \le |s| \le 10^5$), where $|s|$ is the length of the string $s$.

The second line of each test case contains the string $t$ ($|s| \le |t| \le 10^5$).

Both strings consist of lowercase English letters only.

The sum of $|t|$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single string: the lexicographically smallest reordering of letters in the string $t$ that contains $s$ as a subsequence. If no such string exists, print "Impossible" instead.

对于每个测试用例，输出一个字符串：字符串 $t$ 的字母的字典序最小重排，使得该重排包含 $s$ 作为子序列。如果不存在这样的字符串，则输出 "Impossible"。

In the first test case, $\mathtt{abc}\,\mathtt{dcbe}\,\mathtt{ef}$ contains $\mathtt{dcbe}$.

In the second test case, $\mathtt{aaaaa}\,\mathtt{baba}\,\mathtt{bcc}\,\mathtt{dab}$ also contains $\mathtt{babadab}$.

It can be proven that these are the lexicographically smallest strings satisfying the given condition.

In the third test case, no rearrangement of letters in $t$ contains $s$.

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

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

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

在第三个测试用例中，$t$ 中字母的任意重排均不包含 $s$。