Censoring

Time limit1sMemory limit256 MB

Summary

Repeatedly delete the leftmost occurrence of any of N forbidden words from string S until none remains and print the result.

Level: Medium7 of 10
Topics: String matching, Stack, Simulation
Solved: No attempts yet

Problem

One issue of a magazine has been flattened into a single string $S$ made of lowercase letters. Some words must not appear in it, so the $N$ censored words $t_1$ to $t_N$ have to be deleted from $S$ .

Censoring works like this. Find the occurrence of a censored word in $S$ that starts at the smallest index, and delete that occurrence. Repeat until $S$ contains no occurrence of any censored word. Deleting one occurrence joins the characters around it, so a censored word that was not there before can appear.

No censored word is a substring of another censored word. At every step the occurrence with the smallest start index is therefore unique.

Print $S$ after censoring stops.

Input

The first line contains the string $S$ . It consists of lowercase letters and its length is at most $10^5$ .

The second line contains $N$ , the number of censored words.

Each of the next $N$ lines contains one censored word, $t_1$ to $t_N$ in order. Every word consists of lowercase letters, and the total length of the $N$ words is at most $10^5$ .

Output

Print $S$ after every deletion is done. $S$ never becomes empty during the process.

Examples4

Example 1

Input

begintheescapexecutionatthebreakofdawn
2
escape
execution

Expected output

beginthatthebreakofdawn

Example 2
Input
```
xaabbx
1
ab
```
Expected output
```
xx
```
Example 3
Input
```
abcdefg
3
hij
klm
xyz
```
Expected output
```
abcdefg
```
Example 4
Input
```
abababa
1
b
```
Expected output
```
aaaa
```