#include<bits/stdc++.h>

 using namespace std;

 const int N=;

 string a[N],b[N],c[N];

 int main()

 {

     //freopen("a.in","r",stdin);

     int n,m;

     scanf("%d%d",&n,&m);getline(cin,a[]);

     for(int i=;i<=n;i++) getline(cin,a[i]);

     string s;

     for(int i=;i<=m;i++)

     {

         getline(cin,s);

         int j=;

         b[i]="{{ ";

         for(j=;j<s.size();j++)

         {

             if(s[j]==' ') {j+=;break;}

             b[i]+=s[j];

         }

         b[i]+=" }}";

         c[i]="";

         for(;j<s.size()-;j++) c[i]+=s[j];

     }

     // for(int i=1;i<=n;i++)

         // cout << b[i] << ' ' << c[i] << endl;

     for(int i=;i<=n;i++)

     {

         string token="";

         for(int j=;j<a[i].size();j++)

         {

             bool ok=;

             if(j+<a[i].size() && a[i][j]=='{' && a[i][j+]=='{')

             {

                 for(int k=;k<=m;k++)

                 {

                     if(a[i].compare(j,b[k].size(),b[k])==)

                     {

                         ok=;

                         j+=b[k].size()-;

                         token+=c[k];

                         break;

                     }

                 }

                 if(!ok)

                 {

                     for(int k=j+;k<a[i].size();k++)

                         if(a[i][k]=='}' && a[i][k-]=='}' && a[i][k-]==' ') {j=k;ok=;break;}

                 }

             }

             if(!ok) token+=a[i][j];

         }

         cout << token << endl;

     }

     return ;

 }