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:

It is in L.

It is different from w.

Their common suffix is as long as possible.

Out of all words that satisfy the previous points, u is the lexicographically smallest one. 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).

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.

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

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.

IPSC 2008 sample