A. Иголка в стоге сена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам повезло узнать ответ на все важные вопросы в мире. На этот раз ответ — это строка $$$s$$$, состоящая только из строчных латинских букв. Вы хотите спрятать эту строку.

У вас есть другая строка $$$t$$$, также состоящая только из строчных латинских букв. Вам нужно переупорядочить буквы в $$$t$$$, чтобы строка $$$s$$$ встречалась хотя бы один раз в $$$t$$$ как подпоследовательность$$$^{\text{∗}}$$$. Среди всех возможных перестановок $$$t$$$, содержащих $$$s$$$ как подпоследовательность, найдите лексикографически наименьшую$$$^{\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$$$ как подпоследовательность. Если такой строки не существует, выведите «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$$$.