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