CF633C Spy Syndrome 2

在观察了“Spy Syndrome”的结果后，Yash 认识到了自己的错误。他现在相信，像 Siddhant 这样的超级间谍绝不会使用像恺撒密码那样基础且古老的密码。经过数周对 Siddhant 所用句子的研究，Yash 发现了一种新的加密技术。 对于一个给定的句子，加密过程如下： 1. 将句子的所有字母转换为小写。 2. 分别将句子中的每个单词单独反转。 3. 移除句子中的所有空格。 例如，对于句子 Kira is childish and he hates losing 加密后得到的字符串是： ariksihsidlihcdnaehsetahgnisol 现在，Yash 得到了一个已经加密的字符串和一个单词列表。请你帮助他还原出一个仅由列表中的单词组成的原始句子。注意，每个单词都可以在句子中重复使用多次。

第一行包含一个整数 $n$（$1 \leq n \leq 10000$），表示密文的长度。 第二行包含 $n$ 个小写英文字母，表示密文 $t$。 第三行包含一个整数 $m$（$1 \leq m \leq 100000$），表示提供的单词数量。接下来的 $m$ 行，每行包含一个非空单词 $w_{i}$（$|w_{i}| \leq 1000$），由大小写英文字母组成。保证所有单词的总长度不超过 $1000000$。

输出一行，即还原得到的原始句子。保证至少存在一个解。如果有多种答案，你可以输出任意一种。

在样例 2 中，可能有多个合法输出，比如“HI there HeLLo”和“HI there hello”，你可以输出其中任意一个。 由 ChatGPT 5 翻译