Jeremy does not have a good filter on his speech. As a result, he often gets banned on online platforms due to his profanity. Jeremy, tired of this, wishes to have a program that automatically replaces any bad words he says with family-friendly alternatives. He has enlisted you to complete this task, and has thus given you a list of ~N~ bad words he might say. Next to each bad word, there is a clean word that he wants to replace all instances of that bad word with. Can you give him a hand?

Note: This problem does not actually use any profane language in its input or output.

Input Specification

The first line will be a string ~S~ containing Jeremy's message. ~S~ will always contain lowercase letters and spaces only and will always be less than ~2000~ characters in length.
The next line will be an integer ~N~ ~(0 \le N \le 100)~, representing the number of bad words in Jeremy's vocabulary.
The next ~N~ lines will consist of two all-lowercase strings each, ~B~ and ~C~, separated by a space.
It is guaranteed that each word in ~S~ will appear as ~B~ at most once.

Output Specification

One line containing Jeremy's message with all profanity replaced.

Sample Input

i hate school it is so lame and dumb
3
hate dislike
dumb foolish
lame uninteresting

Sample Output

i dislike school it is so uninteresting and foolish