G. Разрешенные буквы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп недавно запустил свою новую идею для стартапа. Ниша довольно свободна, вектор развития звучит еще как многообещающе, поэтому он довольно легко нашел себе инвесторов для поддержки компании. Однако он так и не смог выбрать название стартапа!

На самом деле, Поликарп придумал название, но некоторые изменения ему точно не помешают. Теперь он хочет поменять местами некоторые буквы, чтобы получить лучшее название. Буквы не обязательно должны стоять рядом.

К тому же, каждый из инвесторов выбрал себе по позиции в названии и утвердил список букв, которые могут там стоять. Позиции, выбранные инвесторами попарно различны. Если некоторые позиции не выбраны ни одним инвестором, то там может стоять любая буква.

Наконец, Поликарп уверен, что минимальное лексикографически название — лучшее название. (Ну так а почему, думаете, Google решил стать Alphabet?)

Формально, вам дана строка, состоящая из строчных латинских букв от «a» to «f». Можно менять местами буквы на любых позициях произвольное количество раз (можно и ноль).

Какое минимальное лексикографически название получить такое, что буква на каждой позиции в нем находится среди разрешенных букв?

Если Поликарп не может получить ни одного корректного названия, то выведите «Impossible».

Входные данные

В первой строке содержится строка $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — название, которое придумал Поликарп. Строка состоит только из строчных латинских букв от «a» to «f».

Во второй строке записано одно целое число $$$m$$$ ($$$0 \le m \le |s|$$$) — количество инвесторов.

В $$$i$$$-й из следующих $$$m$$$ строк записано целое число $$$pos_i$$$ и непустая строка разрешенных символов для $$$pos_i$$$ ($$$1 \le pos_i \le |s|$$$). Каждая строка содержит попарно различные буквы от «a» to «f». $$$pos_1, pos_2, \dots, pos_m$$$ попарно различны. Если какая-либо позиция в строке не содержится в требованиях инвесторов, то любая буква может стоять на этой позиции.

Выходные данные

Если Поликарп не может составить никакого корректного названия, то выведите «Impossible».

В противном случае выведите минимальное лексикографически название, которое Поликарп может получить с помощью обменов букв в строке $$$s$$$, такое, что буква на каждой позиции в нем находится среди разрешенных букв.

Примеры
Входные данные
bedefead
5
2 e
1 dc
5 b
7 ef
6 ef
Выходные данные
deadbeef
Входные данные
abacaba
0
Выходные данные
aaaabbc
Входные данные
fc
2
1 cfab
2 f
Выходные данные
cf