← 返回题目列表

Codeforces · 95/A

A. 曲棍球

中文机器翻译题面 查看原题

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