P3121 [USACO15FEB] Censoring G

FJ copied all the articles from a magazine and turned them into a string $s$ of length at most $10^5$. He has a list of $n$ words, denoted by $t_1 \cdots t_n$. He wants to delete these words from $s$. Each time, FJ finds in $s$ the earliest occurrence of any word from the list (the earliest occurrence means the smallest starting position), and then deletes that word from $s$. He repeats this operation until no listed word remains in $s$. Note that deleting a word may cause another listed word to appear in $s$. FJ noticed that within the list, no word is a substring of another, which implies that the starting positions of occurrences of listed words in $s$ are pairwise distinct. Please help FJ perform these operations and output the final $s$.

The first line contains a string, the article $s$. The second line contains an integer, the number of words in the list $n$. Lines $3$ through $(n + 2)$ each contain a string; the string on line $(i + 2)$, $t_i$, denotes the $i$-th word.

Output a single line containing the string $s$ after all operations.

#### Constraints For all test points, it is guaranteed that: - $1 \leq |s|, \sum\limits_{i = 1}^n |t_i|, n \leq 10^5$. - All strings contain only lowercase letters. - After the operations finish, $s$ will not become an empty string. - For all $i \neq j$, $t_i$ is not a substring of $t_j$. Here, for a string $x$, $|x|$ denotes its length. --- #### Hint During the process, a prefix of $s$ may be completely deleted; pay special attention to this. Translated by ChatGPT 5