A16532. Needle in a Haystack
编程题
普及/提高-
知识点
题目描述
你很幸运，知道了世界上所有重要问题的答案。这一次，答案是一个只由小写英文字母组成的字符串 $s$。你希望隐藏这个字符串。
你还有另一个只由小写英文字母组成的字符串 $t$。你需要将 $t$ 的字母重新排列，使得字符串 $s$ 至少作为一个子序列 $^{\text{∗}}$ 出现在 $t$ 中。在所有满足条件（即 $t$ 的某种排列包含 $s$ 作为子序列）的排列中，找到字典序最小 $^{\text{†}}$ 的那个。
$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，如果 $a$ 可以通过删除 $b$ 中的若干（可以为零个或全部）元素，并保持剩余元素的相对顺序得到。
$^{\text{†}}$ 如果字符串 $a$ 是字符串 $b$ 的前缀且 $a \ne b$，或者在第一个不同的位置 $a$ 的该字符字母序在 $b$ 的对应字符之前，则 $a$ 的字典序小于 $b$。
你还有另一个只由小写英文字母组成的字符串 $t$。你需要将 $t$ 的字母重新排列，使得字符串 $s$ 至少作为一个子序列 $^{\text{∗}}$ 出现在 $t$ 中。在所有满足条件（即 $t$ 的某种排列包含 $s$ 作为子序列）的排列中，找到字典序最小 $^{\text{†}}$ 的那个。
$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，如果 $a$ 可以通过删除 $b$ 中的若干（可以为零个或全部）元素，并保持剩余元素的相对顺序得到。
$^{\text{†}}$ 如果字符串 $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$。
每个测试用例的第一行包含字符串 $s$（$1 \le |s| \le 10^5$），其中 $|s|$ 表示字符串 $s$ 的长度。
每个测试用例的第二行包含字符串 $t$（$|s| \le |t| \le 10^5$）。
两个字符串都只包含小写英文字母。
所有测试用例中 $|t|$ 的总和不超过 $10^5$。
输出格式
对于每个测试用例，输出一行，仅包含一个字符串：通过重新排列 $t$ 的字母得到的、包含 $s$ 作为子序列的字典序最小的字符串。如果不存在这样的字符串，输出 “Impossible”。
输入输出样例
输入 #1
3 dcbe bedbaecfc babadab abacabadabacaba babaisyou flagiswin
输出 #1
abcdcbeef aaaaabababccdab Impossible
说明/提示
在第一个测试用例中，$\mathtt{abc}\,\mathtt{dcbe}\,\mathtt{ef}$ 包含了 $\mathtt{dcbe}$。
在第二个测试用例中，$\mathtt{aaaaa}\,\mathtt{baba}\,\mathtt{bcc}\,\mathtt{dab}$ 也包含了 $\mathtt{babadab}$。
可以证明这些字符串是满足条件的字典序最小的字符串。
在第三个测试用例中，无法通过 $t$ 的任意排列得到包含 $s$ 的字符串。
在第二个测试用例中，$\mathtt{aaaaa}\,\mathtt{baba}\,\mathtt{bcc}\,\mathtt{dab}$ 也包含了 $\mathtt{babadab}$。
可以证明这些字符串是满足条件的字典序最小的字符串。
在第三个测试用例中，无法通过 $t$ 的任意排列得到包含 $s$ 的字符串。