Problem1060--「一本通 2.4 练习 2」Censoring

1060: 「一本通 2.4 练习 2」Censoring

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:USACO 2015 Feb. Gold

有一个长度不超过 10510^5105 的字符串 SSS。Farmer John 希望在 SSS 中删掉 nnn 个屏蔽词(一个屏蔽词可能出现多次),这些词记为 t1∼tnt_1\sim t_nt1tn

FJ 在 SSS 中从头开始寻找屏蔽词,一旦找到一个屏蔽词,FJ 就删除它,然后又从头开始寻找(而不是接着往下找)。FJ 会重复这一过程,直到 SSS 中没有屏蔽词为止。注意删除一个单词后可能会导致 SSS 中出现另一个屏蔽词。这 nnn 个屏蔽词不会出现一个单词是另一个单词子串的情况,这意味着每个屏蔽词在 SSS 中出现的开始位置是互不相同的,请帮助 FJ 完成这些操作并输出最后的 SSS


Input

第一行包含一个字符串 SSS
第二行包含一个整数 nnn
接下来的 nnn 行,每行包含一个字符串,第 iii 行的字符串是 tit_iti


Output

一行,输出操作后的 SSS。保证 SSS 不会变成空串。


Sample Input

begintheescapexecutionatthebreakofdawn
2
escape
execution

Sample Output

beginthatthebreakofdawn

HINT

对于全部数据,1≤∑∣ti∣≤105,1≤∣S∣≤1051\le \sum |t_i|\le 10^5,1\le |S|\le 10^51ti105,1S105,保证所有字符串只出现小写字母。


Source/Category


Submit Status