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

Яш хочет взломать используемый Сидхантом шифр. После долгих недель наблюдений он понял, что Сидхант шифрует предложения следующим образом:

  1. Перевести все буквы в нижний регистр.
  2. Каждое слово в предложение заменить на развёрнутое.
  3. Удалить все пробелы.

Например, если взять предложение

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