You have a new professor of graph theory and he speaks very quickly. You come up with the following plan to keep up with his lecture and make notes.

You know two languages, and the professor is giving the lecture in the first one. The words in both languages consist of lowercase English characters, each language consists of several words. For each language, all words are distinct, i.e. they are spelled differently. Moreover, the words of these languages have a one-to-one correspondence, that is, for each word in each language, there exists exactly one word in the other language having has the same meaning.

You can write down every word the professor says in either the first language or the second language. Of course, during the lecture you write down each word in the language in which the word is shorter. In case of equal lengths of the corresponding words you prefer the word of the first language.

You are given the text of the lecture the professor is going to read. Find out how the lecture will be recorded in your notes.


-----Input-----

The first line contains two integers, n and m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 3000) — the number of words in the professor's lecture and the number of words in each of these languages.

The following m lines contain the words. The i-th line contains two strings a_{i}, b_{i} meaning that the word a_{i} belongs to the first language, the word b_{i} belongs to the second language, and these two words have the same meaning. It is guaranteed that no word occurs in both languages, and each word occurs in its language exactly once.

The next line contains n space-separated strings c_1, c_2, ..., c_{n} — the text of the lecture. It is guaranteed that each of the strings c_{i} belongs to the set of strings {a_1, a_2, ... a_{m}}.

All the strings in the input are non-empty, each consisting of no more than 10 lowercase English letters.


-----Output-----

Output exactly n words: how you will record the lecture in your notebook. Output the words of the lecture in the same order as in the input.


-----Examples-----
Input
4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest

Output
codeforces round letter round

Input
5 3
joll wuqrd
euzf un
hbnyiyc rsoqqveh
hbnyiyc joll joll euzf joll

Output
hbnyiyc joll joll un joll

Difficulty: interview

Starter code:

Solutions:
n, m = map(int, input().split())
d = { }
for i in range(m):
    a, b = input().split()
    d[a] = b if len(b) < len(a) else a
for word in input().split():
    print(d[word], end=' ')
print()


n, m = map(int, input().split())
first = dict()
second = dict()
for i in range(m):
    s1, s2 = input().split()
    first[s1] = s2
    second[s2] = s1
    
    
lection = input().split()
for i in lection:
    if len(i) > len(first[i]):
        print(first[i], end = ' ')
    else:
        print(i, end = ' ')


n, m = map(int, input().split())
words = dict()
for i in range(m):
    w1, w2 = map(str, input().split())
    w = w1
    if len(w2) < len(w1):
        w = w2
    words[w1] = w
    words[w2] = w
data = input().split()
for i in range(n):
    print(words[data[i]], end = " ")
    
    

n, m = [int(i) for i in input().split()]
d = dict()
for i in range(m):
    s, s2 = input().split()
    d[s] = s2
for s in input().split():
    if(len(d[s])<len(s)):
        print(d[s],end=' ')
    else:
        print(s,end=' ')


#input

n,m=list(map(int,input().split()))
d_1=[]
d_2=[]
for i in range(m):
	x,y=list(map(str,input().split()))
	d_1.append(x)
	d_2.append(y)

l=[str(x) for x in input().split()]


#variables



#main

for i in range(n):
	if len(d_2[d_1.index(l[i])])<len(l[i]):
		l[i]=d_2[d_1.index(l[i])]



#output
print(''.join([str(l[i])+' ' for i in range(n)]))


n, m = map(int, input().split())
arr = {}
for _ in range(m):
	a, b = map(str, input().split())
	if(len(a) > len(b)):
		arr[a] = b
lect = input().split()
res = []
for i in lect:
	if i in arr:
		res.append(arr[i])
	else:
		res.append(i)
print(' '.join(res))

inp = input().split(' ')
change = {}
for x in range(int(inp[1])):
    a = input().split()
    if len(a[1])<len(a[0]):
        change[a[0]] = a[1]
    else:
        change[a[0]] = a[0]
b = input().split(' ')
out = ""
c = b.pop(0)
out = out + change[c]
for y in b:
    out = out + ' ' + change[y]
print(out)


n, m = [int(_) for _ in input().split()]
trans = {}

def better(a,b):
    if len(a) <= len(b):
        return a
    else:
        return b
    
for i in range(m):
    a,b = input().split()
    trans[a] = better(a,b)
    trans[b] = better(a,b)
    
l = input().split()
s = ""
for i in l:
    s += trans[i] + " "
    
print(s)


# B

l = input().split()
n = int(l[0])
m = int(l[1])
x = []
y = []
for i in range(m):
    inp = input().split()
    x.append(inp[0])
    if len(inp[1])<len(inp[0]):
        y.append(inp[1])
    else:
        y.append(inp[0])
prof = input().split()
for i in range(n):
    prof[i] = y[x.index(prof[i])]
    
s = prof[0]
for i in range(1,n):
    s += ' '+prof[i]

print(s)


##n = int(input())
n, m = list(map(int, input().split()))
##s = input()
##A = list(map(int, input().split()))
A = dict()
for i in range(m):
    s, d = input().split()
    A[s] = d
S = input().split()
d = ''
for i in range(n):
    if len(S[i]) <= len(A[S[i]]):
        d += S[i] + ' '
    else:
        d += A[S[i]] + ' '
print(d)


dictx = {}
a, b = list(map(int, input().split(' ')))

for i in range(b):
    x, y = list(map(str, input().split(' ')))
    if len(y) < len(x):
        dictx[x] = y
        dictx[y] =y
    else:
        dictx[y] = x
        dictx[x] = x

god = list(map(str, input().split(' ')))
strx = [dictx[i] for i in god]
print(' '.join(strx))


first_line = list(map(int, input().split(' ')))
length_speech = first_line[0]
dictionary_len = first_line[1]

dict = {}
for i in range(dictionary_len):
	line = list( input().split(' '))
	dict[line[0]] = line[1]

speech = list( input().split(' '))
#print( dict )
#print (speech)

for i in range(len(speech)):
	w = speech[i]
	if len(dict[w]) < len(w):
		speech[i] = dict[w]
print(' '.join(speech))

def main():
    n, m = map(int, input().split())
    d = {}
    for _ in range(m):
        a, b = input().split()
        d[a] = d[b] = b if len(a) > len(b) else a
    print(' '.join([d[_] for _ in input().split()]))


def __starting_point():
    main()
__starting_point()

'''from math import *
int(input())
list(map(int,input().split()))'''
def main():
	n, m = list(map(int,input().split()))
	trans = {}
	for _ in range(m):
		temp = list(input().split())
		a, b = temp[0],temp[1]
		if len(a) <= len(b):
			trans[a] = a
		else:
			trans[a] = b
	lecture = list(input().split())
	notes = ''
	for x in lecture:
		notes += (trans[x]+' ')
	print(notes)


def __starting_point():
	main()


__starting_point()

n, m = list(map(int, input().split()))
d = dict([input().split() for _ in range(m)])
print(" ".join([min((w, d[w]), key=len) for w in input().strip().split()]))


n,m=map(int,input().split())
d={}
for i in range(m):
    a,b=input().split()
    d[a]=b
for s in input().split():
    if(len(s)>len(d[s])):
       print(d[s],end=' ')
    else:
       print(s,end=' ')

n, m = map(int, input().split())
st1 = { }
st2 = { }
for i in range(m):
    s = input().split()
    w1, w2 = s[0], s[1]
    st1[w1] = w2
    st2[w2] = w1
test = input().split()
for x in test:
    w1 = x
    f = False
    if w1 in st1:
        f = True # w1 - first lang
        w2 = st1[w1]
    else:
        w2 = st2[w1]
    if len(w1) < len(w2):
        print(w1, end=' ')
    elif len(w2) < len(w1):
        print(w2, end=' ')
    else:
        print(w1 if f else w2, end=' ')
    



def intput():
    return [int(x) for x in input().split(" ")]


def main(lecture, mapping):
    ans = []
    for word in lecture:
        ans.append(mapping[word])
    print(' '.join(ans))


def parse():
    _, words = intput()
    mapping = {}

    for _ in range(words):
        l1, l2 = input().split(" ")
        lm = l2 if len(l2) < len(l1) else l1
        mapping[l1] = lm

    lecture = input().split(" ")
    return lecture, mapping

main(*parse())


n,m=map(int,input().split())


a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    l,r=input().split()
    a[i]=l
    b[i]=r
    if len(l)<=len(r):
        c[i]=l
    else:
        c[i]=r

s=list(input().split())

answer=""
for i in range(n):
    if s[i] in a:
        x=a.index(s[i])
    else:
        x=b.index(s[i])
    answer+=c[x]
    answer+=" "
tr=len(answer)
print(answer[0:tr-1])

import functools

n,m = (int(x) for x in input().split(" "))

lang = {}

for i in range(0,m):
    a,b = (x for x in input().split(" "))
    if len(a) > len(b) :
        lang[a] = b
    else:
        lang[b] = a

def shorter(x):
    if x in lang:
        return lang[x]
    else:
        return x

print(functools.reduce(lambda x,y: x+" "+y,[shorter(x) for x in input().split()]))




__author__ = 'Rakshak.R.Hegde'
"""
Created on Dec 24 2014 PM 10:22

@author: Rakshak.R.Hegde
"""

n, m = map(int, input().split())
trans = dict()
for i in range(m):
    x, y = input().split()
    trans[x] = y
lect = input().split()
ans = ''
for w in lect:
    ans += min(w, trans[w], key=lambda x: len(x)) + ' '
print(ans)

n,m = map(int,input().split())
s = {}
for i in range(m):
    stemp = input().split()
    s[stemp[0]] = stemp[1]
    s[stemp[1]] = stemp[0]
st = input().split()
for i in range(len(st)):
    if(i == len(st)-1):
        if(len(s[st[i]]) >= len(st[i])):
            print(st[i])
        else:
            print(s[st[i]])
    else:
        if(len(s[st[i]]) >= len(st[i])):
            print(st[i],end=' ')
        else:
            print(s[st[i]],end=' ')
    



n,m=input().split()
n,m=int(n),int(m)
lis=[]
for i in range(m):
    lis.append(input().split())
def decide(lis):
    if len(lis[0])<=len(lis[1]):
        return lis[0]
    else:
        return lis[1]
dic={}
for i in range(m):
    dic[lis[i][0]]=decide(lis[i])

lec=input().split()
for i in range(n):
    print(dic[lec[i]],end=' ')