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$（$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”。

输入 #1

3
dcbe
bedbaecfc
babadab
abacabadabacaba
babaisyou
flagiswin

输出 #1

abcdcbeef
aaaaabababccdab
Impossible