CF95A Hockey

Petya 非常喜欢冰球。有一天，他在观看冰球比赛时睡着了。在梦中，Petya 被任命为修改一支冰球队名字的人。因此，Petya 得到了原始的队名 $w$ 以及一组被禁止出现的子串 $s_{1}, s_{2}, \ldots, s_{n}$。所有这些字符串均由大小写拉丁字母组成。字符串 $w$ 的长度为 $|w|$，它的字符从 $1$ 到 $|w|$ 编号。 首先，Petya 需要在字符串 $w$ 中找到所有被禁止子串的出现位置。在寻找子串时，不区分字母的大小写。也就是说，字符串 "aBC" 和 "ABc" 被认为是相等的。 接下来，Petya 需要替换所有被这些出现位置覆盖的字母。更准确地说：在位置 $i$ 的某个字母应被替换为其他任意字母，条件是存在一对下标 $l, r$（$1 \leq l \leq i \leq r \leq |w|$），使得子串 $w[l \ldots r]$（不区分大小写）包含在集合 $s_{1}, s_{2}, \ldots, s_{n}$ 中。在替换时，字母的大小写应保持不变。Petya 不允许替换未被任何禁止子串覆盖的位置上的字母。 对于冰球运动员来说，字母 $letter$（无论大小写）被认为是幸运的。因此，Petya 应该进行替换，使得最终字符串中 $letter$ 出现的次数尽可能多。如果有多种方案，输出字典序最小的那个。 注意，字母替换只进行一次。如果经过替换后，字符串中出现了新的禁止子串，Petya 不再理会。

第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示被禁止子串的数量。接下来的 $n$ 行，每行一个禁止子串。再下一行包含字符串 $w$。所有 $n+1$ 行均为非空字符串，由大小写拉丁字母组成，长度不超过 $100$。最后一行包含一个小写字母 $letter$。

输出一行，表示经过修改后的最大 $letter$ 数量且字典序最小的队名字符串。 字典序比较采用现代编程语言中的标准 $

由 ChatGPT 5 翻译