#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<vector>

using namespace std;

int n,m;
vector<string> strs;
unordered_map<string,string> vars;

int main()
{
    cin>>n>>m;
    getchar(); //如果用getline()要过滤掉之前输入的回车
    while(n--)
    {
        string str;
        getline(cin,str);
        strs.push_back(str);
    }
    while(m--)
    {
        string key,value;
        cin>>key;
        char c;
        //getchar()读取单个字符
        while(c=getchar(),c!='\"');
        while(c=getchar(),c!='\"') value +=c;
        vars[key] = value;
    }

    for(auto& str:strs)
    {
        for(int i = 0; i<str.size();)
            if(i+1 < str.size() && str[i] == '{' && str[i+1] == '{')
            {
                int j = i+3;
                string key;
                while(str[j] !=' '|| str[j+1] !='}' || str[j+2] !='}')
                    key += str[j++];
                cout<<vars[key];
                i = j+3;
            }
            else cout<<str[i++];
        cout<<endl;
    }

    return 0;
}