#include <bits/stdc++.h>
using namespace std;

struct node {
	string a;
	string b;
} str[5005];

int main() {
	int n, m, l1 = 0, r1, l2, r2;
	cin >> n >> m;
	string s[5005], c, t;
	for (int i = 1; i <= n; i++) {
		cin >> t >> str[i].b;
		str[i].a = "{" + t + "}";

	}
	for (int i = 1; i <= m + 1; ++i) {
		getline(cin, t);
		for (int j = 1; j <= n; j++) {
			if (t.find(str[j].a) != -1) {
				r1 = t.find(str[j].a);
				l2 = t.find(str[j].a) + str[j].a.size() - 1;
				r2 = t.size() - t.find(str[j].a) - str[j].a.size();
				t = t.substr(l1, r1 ) + str[j].b + t.substr(l2 + 1, r2);
			}
//				cout << t.substr(0, t.find(str[j].a)) << str[j].b  << endl;
		}
		cout << t << endl;
//

	}


}