A perfect rhyme is not a crime,
it is something that exceeds time, 
a bit of science, a piece of art, 
soft as a pillow, sharp as a dart.

Everyone tried it, but only few chosen ones succeeded. It is a hard task with an unclear path, but a famous end – should you reach it. Many compare it to finding the Holy Grail, or even to finding Waldo. The task is to find a perfect rhyme.

Problem specification

Given is a wordlist L, and a word w. Your task is to find a word in L that forms a perfect rhyme with w. This word u is uniquely determined by these properties:

Notes

A prefix of a word is any string that can be obtained by repeatedly deleting the last letter of the word. Similarly, a suffix of a word is any string that can be obtained by repeatedly deleting the first letter of the word.

For example, consider the word different.

This word is both its own prefix and suffix. Its longest other prefix is differen, and its longest other suffix is ifferent. The string rent is its yet another, even shorter suffix. The strings eent and iffe are neither prefixes nor suffixes of the word different.

Let u and v be two different words. We say that u is lexicographically smaller than v if either u is a prefix of v, or if i is the first position where they differ, and the i-th letter of u is earlier in the alphabet than the i-th letter of v.

For example, dog is smaller than dogs, which is smaller than dragon (because o is less than r).

Input specification

The input file consists of two parts. The first part contains the wordlist L, one word per line. Each word consists of lowercase English letters only, and no two words are equal.

The first part is terminated by an empty line.

The second part follows, with one query word w per line.

You may assume that in either part of the input, the length of a word will be no more than 30. And the number of words in each part of the input will be no more than 250000. The input file will be less than 5MB.

Output specification

For each query in the input file output a single line with its perfect rhyme. The output must be in lowercase.

Example

input:
perfect
rhyme
crime
time

crime
rhyme

output:
time
crime

In the second test case, there were two candidates that had an equally long common suffix (crime and time), the lexicographically smaller one was chosen.