Algoritmos2023_1_ADS

Como todo computeiro sabemos que você adora um mangá, um desenho animado japonês, karaokê etc, decidimos lhe dar um empurraozinho no aprendizado de uma nova língua com a seguinte tarefa: dado um dicionário Japonês-Português e uma letra de música, escreva um programa que imprima a letra traduzida.
Entrada
A primeira linha de um caso de testes contém um inteiro T que indica o número de instâncias subseqüentes. A primeira linha de cada instância contém dois inteiros M e N (1 ≤ M ≤ 1000000, 1 ≤ N ≤ 1000), que representam o número de palavras no dicionário e o número de linhas na letra da música, respectivamente.
Os próximos M pares de linhas contêm as traduções: a primeira linha de cada par contém a palavra em Japonês, e a segunda linha contém a tradução para o Português (que pode ter uma ou mais palavras). Todas as palavras usam apenas letras minúsculas. Cada palavra em Japonês aparece apenas uma vez em cada instância.
As próximas N linhas contêm a letra da música. Cada linha da letra da música é uma lista de palavras separadas por um espaço (todas as palavras consistem apenas de letras minúsculas). Algumas podem estar vazias, mas nenhuma linha possui espaços no início ou no final.
Nenhuma linha contém mais do que 80 letras.
Saída
Para cada instância imprima as N linhas traduzidas. As palavras que não estão no dicionário devem ser impressas como aparecem na entrada. Imprima uma linha em branco no final de cada tradução.
Nenhuma linha da saída contém mais do que 80 letras.


Exemplo de entrada
1
4 3
galaxy
cara tossiu
kagayaku
canalha do
atsuki
alto que
yuushi
util
o galaxy
o galaxy
o kagayaku atsuki yuushi

Exemplo de saída
o cara tossiu
o cara tossiu
o canalha do alto que ut