Description

Original source: USACO 2015 Feb. Gold

There is a string $S$ with a length not exceeding $10^5$. Farmer John wants to delete $n$ forbidden words (a forbidden word may appear multiple times) from $S$, denoted as $t_1\sim t_n$.

FJ searches for forbidden words in $S$ from the beginning. Once a forbidden word is found, FJ deletes it and then starts searching again from the beginning (rather than continuing from the next position). FJ repeats this process until no forbidden words remain in $S$. Note that deleting a word may cause another forbidden word to appear in $S$. These $n$ forbidden words are designed such that no word is a substring of another, meaning the starting positions of each forbidden word in $S$ are distinct. Please help FJ complete these operations and output the final $S$.

Input Format

The first line contains a string $S$;
The second line contains an integer $n$;
The next $n$ lines each contain a string, where the $i$-th line contains the string $t_i$.

Output Format

A single line containing the modified $S$ after all operations. It is guaranteed that $S$ will not become an empty string.

Sample 1

begintheescapexecutionatthebreakofdawn
2
escape
execution

beginthatthebreakofdawn

Data Range and Hints

For all data, $1\le \sum |t_i|\le 10^5,1\le |S|\le 10^5$. It is guaranteed that all strings consist only of lowercase letters.