Farmer John has taken all of the text from a magazine to create the string S of length at most 10^5 characters. He has a list of censored words t_1 ... t_N that he wishes to delete from S. To do so, FJ finds the earliest occurrence of a censored word in S (having the earliest start index) and removes that instance. He repeats this until there are no more occurrences of censored words. The deletion of one word might create a new occurrence that didn't exist before.

The censored words have the property that no censored word appears as a substring of another, so the censored word with earliest index in S is uniquely defined.

Please help FJ determine the final contents of S after censoring is complete.

Line 1: S. Line 2: N, the number of censored words. The next N lines contain the strings t_1 ... t_N. Each contains lower-case alphabet characters (a..z), and the combined lengths of all these strings are at most 10^5.

The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > February > Gold