描述

文本处理工具，如$awk$和$sed$，允许您基于脚本自动执行一系列编辑操作。

对于这个问题，我们考虑一个特定的情况，在这个情况下，我们希望基于一组固定的规则，在单行文本中执行一系列字符串替换。

每个规则指定要查找的字符串和要替换它的字符串，如下所示。

        Rule  Find  Replace-by 
         1.ban      bab 
         2.baba     be 
         3.ana      any 
         4.ba b     hind the g 

要对给定的文本行执行编辑，请从第一个规则开始。

用$Replace-by$字符串替换文本中第一次出现的$find$字符串，然后尝试在新文本上再次执行相同的替换。

继续，直到查找字符串不再出现在文本中，然后移动到下一个规则。

继续，直到所有规则都被考虑。

请注意：

(1)在搜索查找字符串时，您总是从文本的开头开始搜索。

(2)一旦您完成了使用规则（因为查找字符串不再出现），您永远不会再次使用该规则。

(3)大小写很重要。例如，假设我们以$banana$ $boat$开始并应用这些规则。转换序列如下所示，其中查找字符串的出现用下划线表示，替换用黑体字表示。

注意，规则1使用了两次，然后规则2使用了一次，然后规则3使用了零次，然后规则4使用了一次。

     Before      After 
     banana boat babana boat 
     babana boat bababa boat 
     bababa boat beba boat 
     beba boat   behind the goat 

输入

输入包含一个或多个测试用例，后面是只包含$0$（零）的行，表示文件结束。

每个测试用例以包含规则数量的一行开始，这些规则将在$1$到$10$之间。

每个规则由两行指定，其中第一行是查找字符串，第二行是替换字符串。

在所有规则之后是包含要编辑的文本的一行。

输出

对于每个测试用例，输出一行包含最终编辑的文本。

查找和替换字符串的长度都不超过$80$个字符。

$Find$字符串将至少包含一个字符，但是$replace-by$字符串可能是空的（在输入文件中由空行表示）。

在编辑过程中，文本可能增长到$255$个字符，但最终输出文本的长度将少于$80$个字符。

4
ban
bab
baba
be
ana
any
ba b
hind the g
banana boat
1
t
sh
toe or top
0

behind the goat
shoe or shop

来源

美国中南部1999编程比赛