Description

Farmer John has purchased a subscription to Good Hooves keeping magazine for his cows, so they have plenty of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his cows not see (clearly, the magazine is in need of better editorial oversight).

FJ has taken all of the text from the magazine to create the string $S$. He has a list of censored words $t_1\sim t_N$ that he wishes to delete from $S$. To do so Farmer John finds the earliest occurrence of a censored word in $S$ (having the earliest start index) and removes that instance of the word from $S$. He then repeats the process again, deleting the earliest occurrence of a censored word from $S$, repeating until there are no more occurrences of censored words in $S$.

Note that the deletion of one censored word might create a new occurrence of a censored word that didn't exist before.

Farmer John notes that the censored words have the property that no censored word appears as a substring of another censored word. In particular this means the censored word with earliest index in $S$ is uniquely defined. Please help FJ determine the final contents of $S$ after censoring is complete.

Input Format

The first line will contain $S$.

The second line will contain $N$, the number of censored words.

The next $N$ lines contain the strings $t_1\sim t_N$.

Output format

The string $S$ after all deletions are complete.

begintheescapexecutionatthebreakofdawn
2
escape
execution

beginthatthebreakofdawn

Limit and Hint

For $100\%$ of testcases, $1\le |S|,\sum|t_i|\le 10^5$, $1\le N\le 2000$, each string will only contain lower-case alphabet characters. It is guaranteed that $S$ will not become empty during the deletion process.

Source

USACO February 2015 Contest Gold T2