URI Online Judge | 2825

L as in Atreus!?

By Gabriel Batista Galli, UFFS BR Brazil

Timelimit: 8

In the recently launched and highly acclaimed God of War game, Kratos is now in the realm of Norse mythology trying to leave the past behind. There he met Faye, a woman as mysterious as himself, with whom he had a child: Atreus. But upon the arrival of a stranger, Kratos and his son embark on a journey with unexpected consequences.

Throughout their path, they find many writings on walls, panels, rocks... These writings tell interesting stories about the Norse world and their personalities, but can also advise an unsuspecting traveller. Sadly, Kratos cannot read them, for he is from Sparta and has not bothered learning the various languages of his new home. So Atreus must translate every written message they come across. And Atreus is very knowledgeable about Linguistics, impressing even Mimir, the wisest man alive!

It is not uncommon, though, that they find messages with missing or damaged runes (Norse letters), making it impossible for Atreus to know what they are trying to say. So you, as a clever and enthusiastic player, were chosen to help them out. Your task is to fix those errors so Atreus can read the sayings and both of them will be better prepared for the dangers of this journey.

But how can one accomplish that? Well, Mimir suggests the following: the Poetic Edda and the Prose Edda, two Medieval Icelandic literary works composed mostly of poems, are the two main sources of knowledge about the Norse mythology*. As such, find the words in these collections of poems that are most similar to those Atreus cannot read and use them to correct the sayings. A word w1 is considered more similar to w2 than to w3 if there are fewer letter insertions, deletions and substitutions to do in order to get from w1 to w2 than from w1 to w3.

Input

The input is composed of multiple lines. The first one contains an integer a (1 ≤ a ≤ 103) representing the amount of unique words you have found in an Edda. Then, each of the following a lines contain one such word. The next line contains another integer, l (1 ≤ l ≤ 102), which is the length in words of the writing you must fix. And the last line is the writing itself. Every word in it is separated by a single space.

All words in the input are ASCII-only and have a length ≤ 102. There are no diacritics or punctuation.

Output

The output is a single line containing the corrected message for Atreus to read. It follows the same rules as the input and must end with a line feed ('\n'). Additionally, in the case of a tie between two words, choose the one that first appears among those in the input.

Input Samples Output Samples

7
Tyr
Baldur
Freya
Loki
Mimir
Odin
Thor
1
Thyr

Tyr

13
aware
beware
Freya
God
if
Jormungandr
Kratos
Loki
Mimir
Odin
of
War
war
4
Frwus bAWARE of Odnn

Freya beware of Odin

9
Midgard
Niflheim
Muspelheim
Helheim
Jotunheim
Alfheim
Vanaheim
Svartalfheim
Asgard
1
Midgelheim

Muspelheim