#include <bits/stdc++.h>
using namespace std;
int N, M;
string A, B;
map<string, string> S;
int main() {
  cin >> N >> M;
  while (M--) {
    cin >> A >> B;
    S[A] = B.size() < A.size() ? B : A;
  }
  while (N--) {
    cin >> A;
    cout << S[A] << (N ? " " : "\n");
  }
  return 0;
}
