Legend of Heta

Statement:

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 spellbook, 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 spellbook, 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 spellbook 1 ≤ N ≤ 100). Next N lines contain spells sorted by appearance in the spellbook. 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
Example output:
KAKIKAKAKAKKAKAKU
Example input 2:
HEATHLEDGER
2
HEATH
LEDGER
Example output 2:

Example input 3:
KAPKAPPAPAK
1
KAPPA
Example output 3:
K
Example input 4:
CABAI
3
ABA
AB
B
Example output 4:
CAI
Time and memory limit:

  • 1s
  • 128MB

Problem source: Sphere Online Judge