#include<bits/stdc++.h>

using namespace std;

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

int main()
{
    cin >> n >> m;
    getchar();
    while(n --)
    {
        string str;
        getline(cin, str);
        strs.push_back(str);
    }
    while(m --)
    {
        string key, value;
        cin >> key;
        char c;
        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++];

        }
        puts("");

    }
    return 0;
}