题目内容

在英语中，存在一种称为词根的概念。可以在词根后添加其他字母组成一个更长的单词，这个较长的单词称为该词根的衍生词。

例如，词根 $help$ 后添加字母可以形成单词 $helpful$，因此 $helpful$ 是词根 $help$ 的衍生词。

现在给定一个包含 $n$ 个词根的词典 $dictionary$，以及一个由若干个小写英文字母单词组成的句子 $sentence$。

对于句子中的每一个单词，如果它是词典中某个词根的衍生词，则需要将这个单词替换为对应的词根。

如果一个单词可以由多个词根形成，则使用长度最短的词根进行替换。

如果一个单词不存在符合条件的词根，则保持原单词不变。

请输出完成所有替换后的句子。

输入描述

第一行输入一个整数 $n$，表示词典 $dictionary$ 中词根的数量。

第二行输入 $n$ 个字符串 $dictionary_i$，表示词典中的所有词根，相邻字符串之间用空格分隔。

第三行输入一个字符串 $sentence$，表示需要进行处理的句子。

句子中的所有单词均由小写英文字母组成，相邻单词之间由一个空格分隔。

约束

$1 \le n \le 1000$

$1 \le dictionary_i.length \le 100$

$dictionary_i$ 仅由小写英文字母组成。

$1 \le sentence.length \le 10^6$

$sentence$ 仅由小写英文字母和空格组成。

$sentence$ 中单词的数量满足 $1 \le count \le 1000$。

$sentence$ 中每个单词的长度满足 $1 \le length \le 1000$。

$sentence$ 中相邻两个单词之间恰好有一个空格。

$sentence$ 不包含前导空格和尾随空格。

输出描述

输出一行字符串，表示将句子中所有可以替换的衍生词替换为最短词根后得到的句子。

单词之间使用一个空格分隔。

样例1

输入

3
cat bat rat
the cattle was rattled by the battery

输出

the cat was rat by the bat

说明

单词 $cattle$ 可以由词根 $cat$ 形成，因此替换为 $cat$。

单词 $rattled$ 可以由词根 $rat$ 形成，因此替换为 $rat$。

单词 $battery$ 可以由词根 $bat$ 形成，因此替换为 $bat$。

其他单词没有对应的词根，保持不变。

因此最终得到句子 $the\ cat\ was\ rat\ by\ the\ bat$。

样例2

输入

3
a b c
aadsfasf absbs bbab cadsfafs

输出

a a b c

说明

$aadsfasf$ 可以使用词根 $a$ 替换。

$absbs$ 可以使用词根 $a$ 替换。

$bbab$ 可以使用词根 $b$ 替换。

$cadsfafs$ 可以使用词根 $c$ 替换。

因此最终输出 $a\ a\ b\ c$。