1 2 s 128 MB
The first line of input contains two positive integers N ≤ 5 000 and M ≤ 10 000, the number of words in the dictionary and the number of license plates to be handled. Each of the following N lines contains a word from the dictionary, a string no more than 100 characters long containing only lower case letters from the English alphabet. This is followed by M lines each containing a string of three uppercase letters from the English alphabet, representing a license plate.
For each license plate in the input you should output one line containing either the first valid word in the dictionary or the sentence “No valid word” if no such word exists.
5 3 banana car sand uncharacteristically counterrevolutionaries RRR DNA SND
counterrevolutionaries No valid word sand