번역

간단한 번역 프로그램을 사용하여 서로 다른 두 언어 사이에서 텍스트를 번역한다. 두 언어를 $A$와 $B$라고 하자. 프로그램은 사전에 따라 텍스트를 단어별로 번역한다. 한 단어를 번역할 때 프로그램은 사전에서 그 단어가 처음으로 등장하는 항목을 찾아 그에 따라 번역한다.

이러한 프로그램으로 텍스트를 $A$에서 $B$로 번역한 뒤 다시 $A$로 번역하면 정확히 같은 텍스트를 돌려받는다는 보장은 없다. 이 문제에서는 텍스트가 더 이상 바뀌지 않을 때까지 이 절차를 반복해야 한다. 더 정확히는 다음과 같다.

• $a$를 언어 $A$로 작성된 텍스트(단어의 모음)라고 하자.

• $a$를 $A$에서 $B$로 번역하고, 새 텍스트를 $b$라고 하자.

• $b$를 $B$에서 $A$로 번역하고, 새 텍스트를 $a'$라고 하자.

• $a \not = a'$이면 $a'$로 단계 1부터 다시 시작한다. 그렇지 않으면 텍스트의 번역이 완료된다.

사전과 텍스트가 주어질 때, 위 알고리즘으로 생성되는 텍스트를 출력한다.

첫째 줄에 사전에 있는 단어 수를 나타내는 정수 $N$가 주어진다($1 \leq N \leq 50\,000$).

이어서 단어를 번역하는 방법을 설명하는 $N$개의 행이 주어지며, 각 행에는 두 단어가 있다(각 단어는 문자 a-z만으로 이루어지고 공백은 없다). 한 단어의 길이는 최대 20자이다. 첫 번째 단어는 언어 $A$의 단어이고 두 번째 단어는 언어 $B$의 단어이다.

이어서 번역할 텍스트 문자열의 단어 수를 나타내는 정수 $1 \leq M \leq 100\,000$가 주어진다. 마지막 행에는 번역할 텍스트 문자열이 주어지며, 공백으로 구분된 단어들로 이루어져 있다. 텍스트의 모든 단어가 사전에 존재함이 보장된다.

알고리즘이 완료되었을 때 얻은 텍스트를 한 줄로 출력한다.

그룹 | 점수 | 제한

$1$ | $40$ | $N \leq 100$, $M \leq 100$

$2$ | $30$ | $N \leq 1000$

$3$ | $30$ | 추가 제한 없음

알고리즘은 문장을 다음 단계에 따라 번역한다.

• programmering ar valdigt roligt

• programmering ar valdigt skoj

• programmering ar valdigt kul