#include<bits/stdc++.h>
using namespace std;
// #define fileio
#define IOS
void ___()
{
#ifdef fileio
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef IOS
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #define endl '\n'
#endif
}
#define ll long long
int n,k;
map<string,string> q;
void reads(string &s,char ed='\n')
{
    s.clear();
    char c;
    cin>>c;
    while(c!=ed)
    {
        s.push_back(c);
        cin>>c;
    }
}
int main()
{
    ___();
    cin>>n>>k;
    while(n--)
    {
        string p,val;
        cin>>p>>val;
        q[p]=val;
    }
    while(k--)
    {
        string s,p,t;
        reads(s);
        int l=s.length();
        bool f=false;
        for(int i=0;i<l;i++)
        {
            if(f)
                p+=s[i];
            else
                t+=s[i];
            if(s[i]=='{')
                f=true;
            if(s[i]=='}')
            {
                t+=q[p];
                p.clear();
                f=false;
            }
        }
        cout<<t<<endl;
    }
    return 0;
}