a,b=map(int,input().split())
n=input().split()
k=""
for i in range(b):
    m=input().split()
    n.insert(n.index(m[1]),m[0])
for j in n:
    k=k+j+" "
print(k[:-1])