Farmer John bought a subscription to Good Hooveskeeping magazine for his cows. Unfortunately, the last issue contains an inappropriate article - how to cook a steak. FD doesn't want his cows to read it.
The FD took the text of the log, created a string S with a length of no more than 10^5 characters. He has a list of words t_1, t_2, ..., t_N that he wants to remove from S. Therefore, the FD finds the nearest occurrence of a word from the list T (that is, with the smallest index) and removes it from S. Then he continues this process again , until there are no words in T left in S. Note that deleting a word may create a new occurrence of a word in T that did not exist before.
FD noticed that words from the list T have the property that none of them is a substring of another word from T. In particular, this means that the occurrence of a word from T in S is always uniquely determined before. Please help the FD determine the final content of string S.
INPUT FORMAT:
The first line contains S. The second line contains N - the number of words to be deleted. The next N lines contain the lines t_1, t_2, ..., t_N. Each line contains only small Latin letters (a..z) and the total length of all lines will not exceed 10^5.
OUTPUT FORMAT:
Row S after all deletions. It is guaranteed that S will not become empty.
|
Enter |
Output |
|
begintheescapexecutionatthebreakofdawn
2
escape
execution
|
beginthatthebreakofdawn |