Character Conversion

Interview

Time limit1sMemory limit128 MB

Summary

Map each character according to a conversion table where every replacement happens exactly once, and print the resulting string.

Level: Easy3 of 10
Topics: Hash map, Implementation, String
Solved: No attempts yet

Problem

Write a program that converts data according to a given conversion table.

Each character used in the data is a letter or a digit; letters are case-sensitive (uppercase and lowercase are distinguished). The characters listed in the conversion table appear in no particular order.

Each row of the conversion table contains two single characters (not strings) separated by a space: a source character and a target character. Whenever the source character of some row appears in the data, that character is replaced by the corresponding target character and printed. Each conversion happens exactly once: even if a converted character then matches the source character of some row, it is not converted again. A character that does not appear in the conversion table is printed unchanged.

Input

The first line contains the number of rows $n$ in the conversion table. Each of the next $n$ lines contains two characters (a source character and a target character) separated by a space. The next line contains the number of data lines $m$ ( $m < 10^8$ ), and each of the following $m$ lines contains a single character.

Output

Print the converted string on a single line with no spaces or line breaks in the middle, followed by a trailing newline.

Examples1

Example 1

Input

3
A a
0 5
5 4
10
A
B
C
0
1
4
5
a
b
A

Expected output

aBC5144aba