근로장학생

하루는 문장 안에 있는 영어 단어를 찾아 그 뜻을 알려주는 프로그램을 만드는 근로장학생이 되었다.

하지만 하루는 너무 귀찮아서 프로그램을 만들지 않았고, 제작 마감 하루 전에 당신에게 급하게 프로그램 제작을 도와달라고 요청했다. 하루를 도와주자.

• 각 정보는 $(Q_i, A_i)$로 이루어져 있으며, $Q_i$는 영어 단어, $A_i$는 그 단어의 뜻이다.
• $N$개의 정보와 $M$개의 문장이 주어질 때, 프로그램은 각 문장에 대해 다음과 같이 답한다.
  • 문장 $S$의 가장 왼쪽 문자의 위치를 $1$, 가장 오른쪽 문자의 위치를 $|S|$라고 하자. 이때 $|S|$는 문장 $S$의 길이이다.
  • 프로그램은 각 문장 $S$를 첫 번째 문자부터 마지막 문자까지 $S_1, S_2, \cdots, S_{|S|}$ 순서로 읽는다.
  • 문장을 읽는 도중, 위치 $k$에서 $k, k+1, \cdots, k+|Q_i|-1$ 위치의 문자를 차례로 이어 붙였을 때 $Q_i$를 만들 수 있다면 $A_i$로 답해야 한다. 위치 $k$에서 만들 수 있는 $Q_i$가 여러 개라면, 사전순으로 앞선 $Q_i$의 $A_i$로 답한다.
  • 한 문장에 대해 답해야 하는 $A_i$는 여러 개일 수 있다.

예를 들어, 정보 (ABC, X), (A, Y), (CDE, Z)가 있고 질문이 ABCDE라면 프로그램은 YXZ로 답해야 한다.

첫 번째 줄에 정보의 개수 $N$과 문장의 개수 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 1\ 000$; $1 \leq M \leq 10$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $Q_i$와 $A_i$가 공백으로 구분되어 주어진다. ($1 \leq |Q_i|, |A_i| \leq 10$; $i \neq j$이면 $Q_i \neq Q_j$)

그다음 줄부터 $M$개의 줄에 걸쳐 문자열 $S_i$가 주어진다. ($1 \leq |S| \leq 100$)

입력되는 모든 문자열은 영어 대문자로만 이루어져 있고, 공백은 없다.

각 문자열 $S_i$에 대해 프로그램이 답해야 하는 문자열을 한 줄에 하나씩 출력한다.

답할 수 있는 문자열이 없다면 대신 -1을 출력한다.