n,t=map(int,input().split())
a=list(input().split())
for i in range(t):
    s=input().split()
    a.insert(a.index(s[1]),s[0])
print(" ".join(a))