BLHETA - Legend of Heta

Heta is a conventional name for the historical Greek alphabet letter Eta (Η) and several of its variants, when used in their original function of denoting the consonant /h/ (Wikipedia). Because of whispers of N'Zoth the corruptor, Heta now wants to destroy all existing alphabets (fiction).

Heta has a spell book containing spells to delete a string. There are several spells in that book. Armed with the spell book, Heta starts his journey to complete his mission. On his way, Heta found a very long string. To delete that string, Heta reads that string letter by letter from the first letter. If at any point he found a substring that's present in his spell book, that spell will be cast and that substring will be destroyed. Then he continues until he reach the end of that string and no more spell can be used. If there are multiple spells that can be used in one time, the spell that appears first in the book is used. Determine what's left of the very long string after Heta is done!

Input

First line is a string containing A-Z. String can contain from 1 to 100000 characters. Next line of input is N, the number of spells in the spell book (1 ≤ N ≤ 100). Next N lines contain spells sorted by appearance in the spell book. Each spell is a string containing A-Z with a length from 1 to 100.

Output

One line containing the string after Heta is done doing his magic.

Example

Input:
KUKUKAKIKUKAKEKKUKAKAKKUKAKUKAKU
2
KEK
UK

Output:
KAKIKAKAKAKKAKAKU
Input:
HEATHLEDGER
2
HEATH
LEDGER

Output:

Input:
KAPKAPPAPAK
1
KAPPA

Output:
K
Input:
CABAI
3
ABA
AB
B

Output:
CAI

Added by:Andy
Date:2016-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:BLPCS3

hide comments
2021-06-27 11:45:26
There can be duplicate strings in the spellbook. Cost me like 15 WA's
2019-09-22 04:59:08
How did you solve this?
2018-09-21 17:11:45
if reaching the second character make us delete AB then why at first we dont delete the B with the third spell to make the string become CAAI?
2016-12-08 12:22:36
@Mohammad_Ali aba comes before ab in the spell book, shouldn't it be removed first?
" If there are multiple spells that can be used in one time, the spell that appears first in the book is used. "

Last edit: 2016-12-08 17:21:25
2016-10-29 20:55:49 Mohammad_Ali
The reason it's CAI is because upon reaching the third character, AB is matched, so we immediately delete A and B, leaving CAI, which doesn't allow us to delete more stuff.
2016-07-30 15:39:23
is there something wrong in 3rd case
i think there should be only CI because ABA is deleted in first spell
2016-07-17 18:49:50
@Andypertamax could you check my solution id=17303409
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.