← 返回题目列表

Codeforces · 633/C

C. 间谍综合症2

中文机器翻译题面 查看原题

在观察了间谍综合症的结果后,亚什意识到了自己方法的错误。他现在认为,像斯丁特这样的超级间谍无法使用像凯撒密码这样基本而古老的密码。在对斯丁特的句子进行了数周的观察后,亚什确定了一种新的密码技术。

对于给定的句子,密码被处理为:

1. 将句子中的所有字母转换为小写。
2. 分别翻转句子中的每个单词。
3. 删除句子中的所有空格。

例如,当这个密码应用于句子时

基拉很幼稚,他讨厌失败

结果字符串是

ariksihsidlihcdnaehsetahgnisol

现在,Yash 得到了一些加密字符串和单词列表。帮助他找出仅使用列表中的单词组成的任何原始句子。请注意,任何给定的单词都可以在句子中多次使用。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 10 000) - 密文的长度。第二行由n个小写英文字母组成——密文t。

第三行包含一个整数 m (1 ≤ m ≤ 100 000) — 破译文本时将考虑的单词数。接下来的 m 行中的每一行都包含一个仅由大小写英文字母组成的非空单词 wi (|wi| ≤ 1 000)。保证所有单词的总长度不超过1 000 000。

输出

打印一行 — 原始句子。保证至少存在一个解。如果有多个解决方案,您可以输出其中任何一个。

示例

输入 #1

30
ariksihsidlihcdnaehsetahgnisol
10
Kira
hates
is
he
losing
death
childish
L
and
Note

输出 #1

Kira is childish and he hates losing

输入 #2

12
iherehtolleh
5
HI
Ho
there
HeLLo
hello

输出 #2

HI there HeLLo

注意

在示例案例 2 中,可能有多个接受的输出,“HI there HeLLo”和“HI There hello”,您可以输出其中任何一个。