/* Učebnice -- řešení v C++ */

#include <cstdio>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;
#define WORD_LEN 1024

struct TRIE_UZEL{
      TRIE_UZEL *potomci[26];
      string *hodnota;
      TRIE_UZEL()
      {
         for(int i=0; i<26; i++)
            potomci[i] = NULL;
         hodnota = NULL;
      }
      ~TRIE_UZEL() { delete hodnota; }
   };

class TRIE
{
private:
   TRIE_UZEL *koren_;
   void smaz(TRIE_UZEL *koren);
public:
   TRIE() { koren_ = new TRIE_UZEL; }
   ~TRIE() { smaz(koren_); }
   void pridej(string &slovo, string &hodnota);
   void najdi(string &slovo, string *&vysledek);
};

// Přidá nové slovo do trie
void TRIE::pridej(string &slovo, string &hodnota)
{
   TRIE_UZEL *akt_koren = koren_;
   for (string::iterator it=slovo.begin();it!=slovo.end();++it)
   {
      if (!akt_koren->potomci[*it-'A'])  // Pokud neexistuje potomek, vytvoříme ho
      {
         akt_koren->potomci[*it-'A'] = new TRIE_UZEL;
      }
      akt_koren = akt_koren->potomci[*it-'A']; //Jdeme do odpovídajícího potomka
   }
   // V koncovém uzlu cesty si uložíme překlad vloženého slova
   akt_koren->hodnota = new string(hodnota);
}

// Nalezne překlad slova, pokud existuje
void TRIE::najdi(string &slovo, string *&vysledek)
{
   TRIE_UZEL *akt_koren = koren_;
   for (string::iterator it=slovo.begin();it!=slovo.end();++it)
   {
      if (!akt_koren->potomci[*it-'A'])
      {
         // Pokud neexistuje potomek, slovo v trii není
         vysledek = NULL;
         return;
      }
      akt_koren = akt_koren->potomci[*it-'A'];
   }
   vysledek = akt_koren->hodnota;
}

// Rekurentně projdeme trii a smažeme z paměti všechny uzly
void TRIE::smaz(TRIE_UZEL *koren)
{
   if (!koren)
      return;
   for(int i=0; i<26; i++)
      smaz(koren->potomci[i]);
   delete koren;
}

int main()
{
   ifstream fin;              // Vstupní soubor
   fin.open("ucebnice.in");
   int N;
   fin >> N;

   TRIE trie;
   string klic, hodnota;
   getline(fin, hodnota);
   for(; N>0; N--)            // Načteme slovník a vytvoříme trii
   {
      getline(fin, klic, ' ');
      getline(fin, hodnota);
      trie.pridej(klic, hodnota);
   }

   string vstup;
   string slovo;
   ofstream fout;             // Výstupní soubor
   fout.open("ucebnice.out");

   // Samotný překlad, načteme celou řádku a rozdělíme ji na slova
   while(getline(fin, vstup ))
   {
      stringstream line_fin(vstup);
      while(getline(line_fin, slovo, ' '))
      {
         string *result;
         trie.najdi(slovo, result);

         if (result)
            fout << *result << ' ';
         else
            fout << slovo << ' ';
      }
      fout << endl;
   }
   fout.close();
   fin.close();

   return 0;
}