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