Xiaoyang's Dictionary

Problem Description

On a distant planet there are two countries, country A and country B, which speak different languages: language A and language B. Xiaoyang is a translator of country B, whose job is to translate articles from language A into language B.

To do his job well, Xiaoyang made a dictionary recording the language-B word for each of $N$ language-A words. Coincidentally, all these words consist only of the 26 lowercase English letters.

Xiaoyang wants you to write a program that helps him translate a passage of language A using this dictionary. The passage consists of punctuation characters `!()-[]{}\|;:'",./?<>` and some language-A words; every word is separated from the next by at least one punctuation character. Your program must replace every language-A word in the passage with its language-B translation. In particular, if a word is not found in the dictionary, replace it with the uppercase word UNK.

For example, suppose Xiaoyang's dictionary contains two language-A words abc and d, whose language-B translations are a and def respectively. Then the language-A passage abc.d.d.abc.abcd. is translated into the language-B passage a.def.def.a.UNK., because the word abcd is not in the dictionary and must be replaced by UNK.

Input Format

The first line contains an integer $N$, the number of dictionary entries. It is guaranteed that $N \le 100$.

The next $N$ lines each contain two strings $A$ and $B$ separated by a single space, representing one language-A word and its language-B translation. All the $A$ words are distinct; both $A$ and $B$ have length at most $10$.

The last line contains a string $S$ to be translated. It is guaranteed that $|S| \le 1000$, and that $S$ contains only lowercase letters and the punctuation characters `!()-[]{}\|;:'",./?<>`.

Output Format

Output one line: the translated result.

Sample Input

Sample Input 1

2
abc a
d def
abc.d.d.abc.abcd

Sample Input 2

3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd

Sample Input 3

1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz

Sample Output

Sample Output 1

a.def.def.a.UNK

Sample Output 2

a,(def)def!-a?xxxx

Sample Output 3

!()-[]{}\|;:'",./?<>UNK

Sample Explanation

For sample 1, the dictionary contains two words: abc translates to a, and d translates to def. The passage abc.d.d.abc.abcd is split by the punctuation . into the word sequence abc, d, d, abc, abcd. The first four words are all found in the dictionary and replaced by a, def, def, a; the last word abcd is not in the dictionary, so it is replaced by UNK. Keeping the original punctuation yields the output a.def.def.a.UNK.

Constraints

• $1 \le N \le 100$
• All language-A words are distinct and have length at most $10$.
• All language-B words have length at most $10$.
• The passage $S$ has length at most $1000$ and consists only of lowercase letters and the punctuation `!()-[]{}\|;:'",./?<>`.