URI Online Judge | 1449

The Fantastic Jaspion

By Wanderley Guimarães, USP Brazil
Timelimit: 1

In 1985 premiered the series Kyojuu Tokusou Juspion (Special Megabeast Investigator Juspion) in the Japanese TV. The series came to Brazil a few years later with the title "O Fantástico Jaspion" (The Fantastic Jaspion), and along with it the fantasy of a space police came to millions of brazilian children. After school the children came back running in the streets (without checking for cars), turned on the TV and dove into the courage, role model, and unquestionable thirst for justice of the Fantastic Jaspion. The trade of comics and the fights for trading cards in school's recess were hitting historical marks. Until then, such feeling had only been stimulated by Chaves (El Chavo) and his companions! Given this intergalactic fever, the inevitable happened. The producers of Jaspion won the Nobel Peace Prize! That's right! The producers won a Nobel Prize. The stories of the great Jaspion were everywhere, and the children had the most beautiful example to follow. World peace was guaranteed. We no longer needed to fear the horrible Satan Gos!

In Brazil there was a child who loved Jaspion's stories! Antonio Capote Melhorança Valente Junior, affectionately nicknamed ACM, was a boy from the south of São Paulo who loved to sing the songs of the great hero. He was so fanatic that he bought a Japanese-Portuguese dictionary and started the hard work of translation. However, the work was unfinished! Some parts of the song still need to be translated. Right now you must be wondering: what is my task in this fabulous problem? OK! Before speaking about your task, invite your team partner to dive with you into the outcome of the story. We need to talk a bit more about ACM. He graduated in Computer Science and works today in the same office as you. You work as a programmer next to this guy! Since we know you like him very much, we are certain you will accept the following task: given a Japanese-Portuguese dictionary and a song lyric, write a program that prints the translated lyric.

Input

The input consists of several instances. The first line of input contains an integer T indicating the number of instances.

The first line of each instance contains two integers M and N (1 ≤ M ≤ 1000000, 1 ≤ N ≤ 1000), which represent the number of words in the dictionary and the number of lines in the song lyric, respectively.

The next M pairs of lines contain the translations: the first line of each pair has the word in Japanese, and the second line has the translation to Portuguese (which can have one or more words). All words use lowercase characters only. Each word in Japanese appears only once in each instance.

The next N lines contain the song lyric. Each line of the lyric is a space separated list of words (all consisting of lowercase characters only). Some lines may be empty, but none has spaces in the beginning or in the end.

No line has more than 80 letters.

Output

For each instance print the N translated lines. The words that are not in the dictionary must be printed as they appear in the input. Print a blank line after each translation, including the last one.

No line in the output has more than 80 letters.

Sample Input Sample Output

2
4 3
galaxy
cara tossiu
kagayaku
canalha do
atsuki
alto que
yuushi
util
o galaxy
o galaxy
o kagayaku atsuki yuushi
3 1
bashulhan
sobre a mesa
hu
esta
hasefer
o livro
hasefer hu bashulhan

o cara tossiu
o cara tossiu
o canalha do alto que util

o livro esta sobre a mesa