#include <bits/stdc++.h>

using namespace std;


string s[5050];
string t;
int a[5050];

int main(){
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i ++){
		cin >> s[i] >> a[i];
	}
	int ans = 0; 
	while (getline(cin, t)){
		int l;
		int flag = 0;
		for (int i = 0; i < t.size(); i ++){
			if (t[i] == '{') l = i, flag = 1;
			if (!flag) cout << t[i];
			if (t[i] == '}'){
				string p = t.substr(l + 1, i - l - 1);
				for (int j = 0; j < n; j ++){
					if (p == s[j]) cout << a[j];
				}
				flag = 0;
			}
		}
		//cout << endl;
		ans ++;
		if (ans == k + 1) break; 
		else cout << endl;
	}
}