Manthan, Codefest 16 |
---|
Закончено |
Яш хочет взломать используемый Сидхантом шифр. После долгих недель наблюдений он понял, что Сидхант шифрует предложения следующим образом:
Например, если взять предложение
Kira is childish and he hates losing
и применить к нему данный шифр, то получится строка
ariksihsidlihcdnaehsetahgnisol
Сейчас у Яша есть зашифрованная строка и список слов. Помогите ему найти какое-нибудь исходное предложение, составленное только из слов, встречающихся в списке. Обратите внимание, что любое слово может быть использовано в предложении сколько угодно раз.
В первой строке входных данных записано число n (1 ≤ n ≤ 10 000) — длина зашифрованной строки. Вторая строка содержит саму зашифрованную строку и состоит из n строчных букв английского алфавита.
В третьей строке записано число m (1 ≤ m ≤ 100 000) — количество слов в списке. В каждой из последующих m строк записано непустое слово wi (|wi| ≤ 1 000), состоящее из строчных и заглавных букв английского алфавита. Гарантируется, что суммарная длина всех слов не превосходит 1 000 000.
Выведите одну строчку, содержащую исходное предложение. Гарантируется, что хотя бы одно решение существует. Если решений несколько, то разрешается вывести любое.
30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note
Kira is childish and he hates losing
12
iherehtolleh
5
HI
Ho
there
HeLLo
hello
HI there HeLLo
Название |
---|