#include <bits/stdc++.h>
using namespace std;
int main(int argc, const char* argv[]) {
  int n, q;
  cin >> n >> q;
  map<string, string> m;
  for (size_t i = 0; i < q; ++i) {
    string s1, s2;
    cin >> s1 >> s2;
    m[s1] = s2;
  }
  string s;
  vector<string> res(n);
  for (size_t k = 0; k < n; ++k) {
    cin >> s;
    if (s.size() <= m[s].size())
      res[k] = s;
    else
      res[k] = m[s];
  }
  for (size_t i = 0; i < res.size(); ++i) cout << res[i] << " ";
  cout << endl;
}
