A. Hockey

Codeforces

IDCF95A

Time2000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

Petya loves hockey very much. One day, as he was watching a hockey match, he fell asleep. Petya dreamt of being appointed to change a hockey team's name. Thus, Petya was given the original team name _w_ and the collection of forbidden substrings _s_1, _s_2, ..., _s__n_. All those strings consist of uppercase and lowercase Latin letters. String _w_ has the length of |_w_|, its characters are numbered from 1 to |_w_|. First Petya should find all the occurrences of forbidden substrings in the _w_ string. During the search of substrings the case of letter shouldn't be taken into consideration. That is, strings "_aBC_" and "_ABc_" are considered equal. After that Petya should perform the replacement of all letters covered by the occurrences. More formally: a letter in the position _i_ should be replaced by any other one if for position _i_ in string _w_ there exist pair of indices _l_, _r_ (1 ≤ _l_ ≤ _i_ ≤ _r_ ≤ |_w_|) such that substring _w_\[_l_ ... _r_\] is contained in the collection _s_1, _s_2, ..., _s__n_, when using case insensitive comparison. During the replacement the letter's case should remain the same. Petya is not allowed to replace the letters that aren't covered by any forbidden substring. Letter _letter_ (uppercase or lowercase) is considered lucky for the hockey players. That's why Petya should perform the changes so that the _letter_ occurred in the resulting string as many times as possible. Help Petya to find such resulting string. If there are several such strings, find the one that comes first lexicographically. Note that the process of replacements is not repeated, it occurs only once. That is, if after Petya's replacements the string started to contain new occurrences of bad substrings, Petya pays no attention to them. ## Input The first line contains the only integer _n_ (1 ≤ _n_ ≤ 100) — the number of forbidden substrings in the collection. Next _n_ lines contain these substrings. The next line contains string _w_. All those _n_ + 1 lines are non-empty strings consisting of uppercase and lowercase Latin letters whose length does not exceed 100. The last line contains a lowercase letter _letter_. ## Output Output the only line — Petya's resulting string with the maximum number of letters _letter_. If there are several answers then output the one that comes first lexicographically. The lexicographical comparison is performed by the standard < operator in modern programming languages. The line _a_ is lexicographically smaller than the line _b_, if _a_ is a prefix of _b_, or there exists such an _i_ (1 ≤ _i_ ≤ |_a_|), that _a__i_ < _b__i_, and for any _j_ (1 ≤ _j_ < _i_) _a__j_ = _b__j_. |_a_| stands for the length of string _a_. [samples]

Petya 非常喜欢冰球。一天，当他观看一场冰球比赛时，他睡着了。Petya 梦见自己被任命为更改一支冰球队的名称。因此，Petya 被赋予了原始球队名称 #cf_span[w] 以及一组禁用子串 #cf_span[s1, s2, ..., sn]。所有这些字符串均由大小写拉丁字母组成。字符串 #cf_span[w] 的长度为 #cf_span[|w|]，其字符编号从 #cf_span[1] 到 #cf_span[|w|]。首先，Petya 应找出 #cf_span[w] 字符串中所有禁用子串的出现位置。在搜索子串时，不应考虑字母的大小写。也就是说，字符串 "_aBC_" 和 "_ABc_" 被视为相等。之后，Petya 应替换所有被出现位置覆盖的字母。更正式地说：如果对于位置 #cf_span[i] 在字符串 #cf_span[w] 中存在一对索引 #cf_span[l, r]（#cf_span[1 ≤ l ≤ i ≤ r ≤ |w|]），使得子串 #cf_span[w[l ... r]] 在集合 #cf_span[s1, s2, ..., sn] 中（使用不区分大小写的比较），则位置 #cf_span[i] 的字母应被替换为任意其他字母。在替换过程中，字母的大小写应保持不变。Petya 不允许替换未被任何禁用子串覆盖的字母。字母 #cf_span[letter]（大写或小写）被认为是冰球运动员的幸运字母。因此，Petya 应进行更改，使得结果字符串中 #cf_span[letter] 出现的次数尽可能多。帮助 Petya 找到这样的结果字符串。如果有多个这样的字符串，则找出字典序最小的那个。请注意，替换过程仅执行一次，不会重复。也就是说，即使 Petya 的替换后字符串中出现了新的禁用子串，Petya 也不予理会。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——禁用子串集合中的子串数量。接下来的 #cf_span[n] 行包含这些子串。下一行包含字符串 #cf_span[w]。这 #cf_span[n + 1] 行均为非空字符串，由大小写拉丁字母组成，长度不超过 #cf_span[100]。最后一行包含一个小写字母 #cf_span[letter]。输出仅一行——Petya 的结果字符串，其中 #cf_span[letter] 的出现次数最多。如果有多个答案，则输出字典序最小的那个。字典序比较由现代编程语言中的标准 < 运算符执行。字符串 #cf_span[a] 字典序小于字符串 #cf_span[b]，当且仅当 #cf_span[a] 是 #cf_span[b] 的前缀，或者存在某个 #cf_span[i]（#cf_span[1 ≤ i ≤ |a|]），使得 #cf_span[ai < bi]，且对任意 #cf_span[j]（#cf_span[1 ≤ j < i]）都有 #cf_span[aj = bj]。#cf_span[|a|] 表示字符串 #cf_span[a] 的长度。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——禁用子串集合中的子串数量。接下来的 #cf_span[n] 行包含这些子串。下一行包含字符串 #cf_span[w]。这 #cf_span[n + 1] 行均为非空字符串，由大小写拉丁字母组成，长度不超过 #cf_span[100]。最后一行包含一个小写字母 #cf_span[letter]。 ## Output 输出仅一行——Petya 的结果字符串，其中 #cf_span[letter] 的出现次数最多。如果有多个答案，则输出字典序最小的那个。字典序比较由现代编程语言中的标准 < 运算符执行。字符串 #cf_span[a] 字典序小于字符串 #cf_span[b]，当且仅当 #cf_span[a] 是 #cf_span[b] 的前缀，或者存在某个 #cf_span[i]（#cf_span[1 ≤ i ≤ |a|]），使得 #cf_span[ai < bi]，且对任意 #cf_span[j]（#cf_span[1 ≤ j < i]）都有 #cf_span[aj = bj]。#cf_span[|a|] 表示字符串 #cf_span[a] 的长度。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of forbidden substrings. Let $ S = \{s_1, s_2, \dots, s_n\} $ be the set of forbidden substrings, each $ s_i \in \Sigma^* $, where $ \Sigma $ is the set of uppercase and lowercase Latin letters. Let $ w \in \Sigma^* $ be the original team name, with $ |w| = m $. Let $ c \in \{a, b, \dots, z\} $ be the target lucky lowercase letter. Let $ \text{lower}(x) $ denote the case-insensitive version of string $ x $ (all characters converted to lowercase). **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 1 \leq |s_i| \leq 100 $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq |w| \leq 100 $ 4. All strings consist only of Latin letters. **Coverage Set** Define the set of covered positions: $$ I = \left\{ i \in \{1, \dots, m\} \mid \exists\, l, r \text{ s.t. } 1 \leq l \leq i \leq r \leq m \text{ and } \text{lower}(w[l:r]) \in \text{lower}(S) \right\} $$ where $ w[l:r] $ is the substring from index $ l $ to $ r $ (1-indexed), and $ \text{lower}(S) = \{ \text{lower}(s) \mid s \in S \} $. **Objective** Construct a string $ w' \in \Sigma^* $ such that: - For each $ i \notin I $: $ w'_i = w_i $ (unchanged). - For each $ i \in I $: $ w'_i \in \{ w_i, \text{upper}(c), \text{lower}(c) \} $ if $ w_i $ is a letter, and $ w'_i $ must preserve the case of $ w_i $: - If $ w_i $ is uppercase, then $ w'_i \in \{ w_i, \text{upper}(c) \} $ - If $ w_i $ is lowercase, then $ w'_i \in \{ w_i, \text{lower}(c) \} $ - Maximize the total count of occurrences of $ c $ in $ w' $ (i.e., both $ c $ and $ C $ count as $ c $). - Among all such strings, choose the lexicographically smallest one. **Output** The string $ w' $ satisfying the above.

Samples

Input #1

3
bers
ucky
elu
PetrLoveLuckyNumbers
t

Output #1

PetrLovtTttttNumtttt

Input #2

4
hello
party
abefglghjdhfgj
IVan
petrsmatchwin
a

Output #2

petrsmatchwin

Input #3

2
aCa
cba
abAcaba
c

Output #3

abCacba

API Response (JSON)

{
  "problem": {
    "name": "A. Hockey",
    "description": {
      "content": "Petya loves hockey very much. One day, as he was watching a hockey match, he fell asleep. Petya dreamt of being appointed to change a hockey team's name. Thus, Petya was given the original team name _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF95A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya loves hockey very much. One day, as he was watching a hockey match, he fell asleep. Petya dreamt of being appointed to change a hockey team's name. Thus, Petya was given the original team name _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 非常喜欢冰球。一天，当他观看一场冰球比赛时，他睡着了。Petya 梦见自己被任命为更改一支冰球队的名称。因此，Petya 被赋予了原始球队名称 #cf_span[w] 以及一组禁用子串 #cf_span[s1, s2, ..., sn]。所有这些字符串均由大小写拉丁字母组成。字符串 #cf_span[w] 的长度为 #cf_span[|w|]，其字符编号从 #cf_span[1] 到 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of forbidden substrings.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} $ be the set of forbidden substrings, each $ s_i \\in \\Sigma^* $, where $ \\Sigma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments