#include <bits/stdc++.h>
using namespace std;
map<string,string>a;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		s1="{"+s1+"}";
		a[s1]=s2;
	}
	getchar();
	while(m--)
	{
		string s;
		getline(cin,s);
		int p1=0,p2=0;
		while(s.find('{',p1)!=string::npos && s.find('}',p2)!=string::npos)
		{
			s=(s.substr(0,s.find('{',p1))+a[s.substr(s.find('{',p1),(s.find('}',p2)-s.find('{',p1)+1))]+s.substr(s.find('}',p2)+1,s.length()-s.find('}',p2)));
			p1=s.find('{',p1)+1,p2=s.find('}',p2)+1;
		}
		
		cout<<s<<endl;
	}
	return 0;
}