Abbreviate Location Names

In this problem, you are given a message composed of several location names in their long forms, along with a list of available location names and their corresponding abbreviations. For each location name in the message, you must use the shorter of the two strings: the given abbreviation or the original long form (if the abbreviation is not strictly shorter than the long form). Your task is to convert the original message into a new message where every location name is replaced by its shortest representation.

More formally, given two integers $n$ and $m$, where $n$ indicates the number of location names in the message and $m$ indicates the number of available location entries, followed by $m$ pairs of strings $L$ and $S$ and finally a sequence of $n$ location names, for each location name $L$ use $S$ if $|S| < |L|$ (where $|\cdot|$ denotes the length of the string), otherwise use $L$. The answer is the resulting sequence joined by spaces.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines:

1. The first line contains two integers $n$ and $m$, representing the number of location names in the message and the number of location abbreviation entries, respectively.

2. The next $m$ lines each contain two strings: the long form $L$ and its abbreviation $S$.

3. The last line contains $n$ space-separated strings representing the location names in the message.

outputFormat

Output a single line to standard output (stdout) containing the shortened message. Each location name in the message is replaced by its shortest representation as defined in the problem statement. The resulting location names should be separated by a single space.## sample

5 3
MOUNTAIN MTN
FOREST FOR
RIVER RIV
MOUNTAIN RIVER RIVER FOREST MOUNTAIN

MTN RIV RIV FOR MTN