Car Game

A long drive gets boring, and one cure is a word game. A round starts when someone reads out loud the three letters on the license plate of an oncoming car. The first player to say a word that contains those three letters in the same order wins the round, and whoever has won the most rounds when the car stops wins the game. The three letters do not have to sit next to each other in the word, only in that order.

You lost badly on the last road trip. This time you prepare in advance. For each set of three letters, find the first word in a dictionary that contains those letters in the same order.

The first line contains the number of words in the dictionary $N$ and the number of license plates to handle $M$ ($1 \le N \le 5000$, $1 \le M \le 10000$).

Each of the next $N$ lines contains one dictionary word, a string of at most 100 lower case English letters. A word printed on an earlier line comes earlier in the dictionary.

Each of the next $M$ lines contains one license plate, a string of three upper case English letters.

Print one line for each license plate. Ignoring letter case, print the first word in the dictionary that contains the three plate letters in the same order. If no such word exists, print No valid word.