Petya非常喜欢曲棍球。有一天,他在观看一场曲棍球比赛时睡着了。佩蒂亚梦想被任命为曲棍球队更改名称。因此,Petya 被赋予了原来的团队名称 w 和禁止子串 s1、s2、...、sn 的集合。所有这些字符串均由大写和小写拉丁字母组成。字符串w的长度为|w|,其字符编号从1到|w|。
首先,Petya 应该找到 w 字符串中所有出现的禁止子字符串。在搜索子字符串期间,不应考虑字母的大小写。也就是说,字符串“aBC”和“ABc”被视为相等。
之后,Petya 应该替换出现的所有字母。更正式地说:如果字符串 w 中的位置 i 存在一对索引 l, r (1 ≤ l ≤ i ≤ r ≤ |w|),则在使用不区分大小写的比较时,子字符串 w[l ... r] 包含在集合 s1, s2, ..., sn 中,则位置 i 中的字母应替换为任何其他字母。更换期间,信件的大小写应保持不变。 Petya 不允许替换未被任何禁止子字符串覆盖的字母。
字母字母(大写或小写)对于曲棍球运动员来说被认为是幸运的。这就是为什么 Petya 应该执行更改,以便该字母在结果字符串中出现尽可能多的次数。帮助 Petya 找到这样的结果字符串。如果有多个这样的字符串,请找到按字典顺序排在第一位的字符串。
请注意,替换过程不会重复,只会发生一次。也就是说,如果在 Petya 替换之后字符串开始包含新出现的坏子字符串,Petya 不会注意到它们。
输入
第一行包含唯一的整数 n (1 ≤ n ≤ 100) — 集合中禁止子字符串的数量。接下来的 n 行包含这些子字符串。下一行包含字符串 w。所有这n+1行都是由大小写拉丁字母组成的非空字符串,长度不超过100。最后一行包含一个小写字母。
输出
输出唯一一行 — Petya 得到的字符串中包含最多字母的字符串。如果有多个答案,则输出按字典顺序排在第一个的答案。
字典顺序比较由现代编程语言中的标准 < 运算符执行。如果 a 是 b 的前缀,或者存在这样的 i (1 ≤ i ≤ |a|),即 ai < bi,并且对于任何 j (1 ≤ j < i) aj = bj,则行 a 按字典顺序小于行 b。 |一个|代表字符串a的长度。
示例
输入 #1
3 bers ucky elu PetrLoveLuckyNumbers t
输出 #1
PetrLovtTttttNumtttt
输入 #2
4 hello party abefglghjdhfgj IVan petrsmatchwin a
输出 #2
petrsmatchwin
输入 #3
2 aCa cba abAcaba c
输出 #3
abCacba