Problem H
Translation
You just got a summer internship at a local translation bureau. However, the job is very boring. They refuse to actually use the human mind to make translations; instead, they get “optimal” translations by directly translating each word from a dictionary. Because this is extremely boring, you want to optimize your job by writing a program.
You will be given a sentence in Swedish, and should translate it to English. You will also be given the dictionary.
Input
The first line of input containts the integer $N$ ($1 \leq N \leq 10^4$), the number of words in the sentence.
The next line of input contains a sentence consisting of $N$ words in Swedish, the sentence that you want to translate.
The following line contains the integer $M$ ($1 \leq M \leq 10^4$), the number of word pairs in the dictionary.
Then follow $M$ lines, each containing a pair of words $a$ and $b$, which means that the Swedish word $a$ should be translated to the english word $b$.
It is guaranteed that each $a$ is unique and that all words in the sentence to translate appears in the dictionary. All words in the input consist of letters a-z and are at most 15 letters long. Some of the words may not be real Swedish or English words.
Output
Print the sentence, where each word has been translated from Swedish to English.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 hej jag gillar ikea 7 hej hello ikea ikea jag i bil car haj shark gillar like bord table |
hello i like ikea |
