Поликарп недавно запустил свою новую идею для стартапа. Ниша довольно свободна, вектор развития звучит еще как многообещающе, поэтому он довольно легко нашел себе инвесторов для поддержки компании. Однако он так и не смог выбрать название стартапа!
На самом деле, Поликарп придумал название, но некоторые изменения ему точно не помешают. Теперь он хочет поменять местами некоторые буквы, чтобы получить лучшее название. Буквы не обязательно должны стоять рядом.
К тому же, каждый из инвесторов выбрал себе по позиции в названии и утвердил список букв, которые могут там стоять. Позиции, выбранные инвесторами попарно различны. Если некоторые позиции не выбраны ни одним инвестором, то там может стоять любая буква.
Наконец, Поликарп уверен, что минимальное лексикографически название — лучшее название. (Ну так а почему, думаете, 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
Название |
---|