Description

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$.

Input Format

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 Format

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

begintheescapexecutionatthebreakofdawn 
2 
escape 
execution 

beginthatthebreakofdawn 

Hint

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