Oh, Sab! P21214

Even though stereotypically associated with psychedellic and hard rock musical acts of the sixties and seventies, recent research suggests that the practice of backmasking is actually older than that, and places its origins in the work of the probably most famous Japanese poet of the Edo period, Matsuo Bashō.

According to Professor John Robert Page at the University of Hindemburg, most of Bashō’s best-known haikus contain at least pagan, if not openly satanic, hidden messages against the publicly accepted Buddhist and Shintoist practices of the time. Some of them are extremely blunt and violent—take for instance these famous verses from the Philippine Stanzas:

In order to support his claims, Doctor Page reported about a press statement preserved at the Japanese National Library, where Bashō’s publisher reiterates that “our books only read in one direction: right-to-left”, allegedly to dismiss rumours about hidden messages in the poet’s work. It is also suspected that these rumours contributed to Bashō’s early retirement and self-imposed confinement to focus on the fishing of mudsharks and some related hobbies.

Input

Input starts with a natural number n, followed by n different words, followed by the number of haikus m, followed by m haikus, one per line. Assume that all words are made up of only lowercase letters, and that each haiku consists of lowercase letters, whitespaces and ‘/’.

Output

For each input haiku, print a line with its hidden message: Consider the reversed haiku (ignoring spaces and slashes), and print any given word that can be found when reading the haiku from left to right, avoiding all overlaps. In case of an overlap, always prefer the word that starts first (at the leftmost position), and longer words in the event of another tie. Separate words with spaces. If a kaiku has no hidden words, just print “-”.

Observation

The expected solution of this problem has time complexity Θ(n · ℓ), where ℓ is the sum of the lenghts of the haikus.