题目描述

一个字符串 $s$ (由英文字母组成)，包含若干个英语单词，但单词之间缺少了空格。根据给定的词典，把字符串中的单词分割开。

其中一种简单的方法叫做最大分词法，其基本思想是优先考虑把字符串首部最长的单词切割出来。

算法流程如下(假设词典中最长词长为 $L$ 个字符)：

对字符串 $s[0\dots n]$，检查子串 $s[0\dots L-1]$ 是否在词典中，如果在的话，把该子串切割出来，构成一个词；如果不在，缩减子串长度，依次检查 $s[0\dots L-1]$, $s[0\dots L-2]$, …,$s[0\dots 1]$ 是否可以构成一个词，直到串首能分割出一个合法单词，或待检查的子串只包含一个字符 $s[0]$，则将该字符分割出来。对剩余子串重复上述过程，直至完成对所有字符的分割。

例如，假设词典中包含 $4$ 个单词： $a,an,and,dog$。

待分割字符串为 $annaandog$，分割结果为：$an\ n\ a\ and\ o\ g$。

( 注：很显然，该算法是一种贪心，不能保证分词结果完全正确或所分出的单词都在词典中。赛后你也可以思考一种做法，实现只要句子是完全可分的，则一定能找到完全分词的方案)

输入格式

输入的第一行包含一个整数 $n(1\leq n \leq 4000)$，代表词典中的词数。

接下来 $n$ 行，每行一个单词 $w$ (只包含小写英文字母， $1\leq |w| \leq 14$)。

接下来一行包含一个待分割字符串 $s(1\leq |s| \leq 5000)$。

输出格式

在一行中输出分词结果，两个单词之间用一个空格分开，最后一个单词后没有空格。行末输出一个换行符。

测试样例

4
a
an
dog
and
annaandog

an n a and o g

6
a
an
email
abandon
absolute
absolutely
abandonabsolutely

abandon absolutely

3
a
an
email
anemail

an email