Censoring (Gold)#11183
Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, giving them plenty of material to read while they wait in the barn during milking sessions. Unfortunately, the latest issue contains a rather inappropriate article about 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 extracted all of the text from the magazine into a string of length at most 10^5 characters. He also has a list of censored words t_1, t_2, \ldots, t_n that he wants to remove from .
To censor the text, Farmer John repeatedly finds the earliest occurrence of any censored word in , where "earliest" means the occurrence with the smallest starting index, and removes that occurrence from . He continues this process until contains no censored words. Note that deleting one censored word may create a new occurrence of another censored word that did not exist before.
Farmer John notes that the censored words have the property that no censored word is a substring of another censored word. In particular, this guarantees that the censored word with the earliest starting index in is uniquely determined.
Please help FJ determine the final contents of after the censoring process is complete.
The first line contains the string . The second line contains an integer , the number of censored words. The next lines contain the strings t_1, t_2, \ldots, t_n.
Each string consists only of lowercase English letters (in the range ), and the sum of the lengths of all censored words is at most 10^5.
Print the string after all deletions are complete. It is guaranteed that will not become empty during the deletion process.
Example 1