Яш хочет взломать используемый Сидхантом шифр. После долгих недель наблюдений он понял, что Сидхант шифрует предложения следующим образом:
Например, если взять предложение
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
12 iherehtolleh 5 HI Ho there HeLLo hello
HI there HeLLo
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач