Яш хочет взломать используемый Сидхантом шифр. После долгих недель наблюдений он понял, что Сидхант шифрует предложения следующим образом:
- Перевести все буквы в нижний регистр.
- Каждое слово в предложение заменить на развёрнутое.
- Удалить все пробелы.
Например, если взять предложение
Kira is childish and he hates losing
и применить к нему данный шифр, то получится строка
ariksihsidlihcdnaehsetahgnisol
Сейчас у Яша есть зашифрованная строка и список слов. Помогите ему найти какое-нибудь исходное предложение, составленное только из слов, встречающихся в списке. Обратите внимание, что любое слово может быть использовано в предложении сколько угодно раз.
Выходные данные
Выведите одну строчку, содержащую исходное предложение. Гарантируется, что хотя бы одно решение существует. Если решений несколько, то разрешается вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note
|
Kira is childish and he hates losing
|
|
2
|
12
iherehtolleh
5
HI
Ho
there
HeLLo
hello
|
HI there HeLLo
|