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

#include <stdio.h>
#include <string.h>

#define WORD_MAX 256	/* Maximální délka slova + 1 */

struct trie_node {
  struct trie_node *next[26];
  char val[WORD_MAX];
};

void add_to_trie(struct trie_node *root, char *word, char *val)
{
  int c = word[0] - 'A';
  if (!root->next[c])
    {
      root->next[c] = malloc(sizeof(struct trie_node));
      memset(root->next[c], 0, sizeof(struct trie_node));
    }
  if (word[1])
    add_to_trie(root->next[c], word+1, val);
  else
    strcpy(root->next[c]->val, val);
}

char *find_in_trie(struct trie_node *root, char *word)
{
  if (!root)
    return NULL;
  else if (!word[0])
    return root->val;
  else
    return find_in_trie(root->next[word[0]-'A'], word+1);
}

int main(void)
{
  FILE *in = fopen("ucebnice.in", "r");
  FILE *out = fopen("ucebnice.out", "w");
  struct trie_node trie_root = { };
  int N;

  fscanf(in, "%d", &N);
  for (int i=0; i<N; ++i)
    {
      char input[WORD_MAX], val[WORD_MAX];
      fscanf(in, "%s%s ", input, val);
      add_to_trie(&trie_root, input, val);
    }

  char word[WORD_MAX];
  int wlen = 0;
  int input;
  do
    {
      input = fgetc(in);
      if (input >= 'A' && input <= 'Z')
	word[wlen++] = input;
      else
	{
	  if (wlen)
	    {
	      word[wlen] = 0;
	      char *val = find_in_trie(&trie_root, word);
	      if (val && val[0])
		fputs(val, out);
	      else
		fputs(word, out);
	      wlen = 0;
	    }
	  if (input != EOF)
	    fputc(input, out);
	}
    }
  while (input != EOF);

  fclose(out);
  fclose(in);
  return 0;
}