407054: GYM102697 025 Write It, Do It

You are the "do-er" for the Science Olympiad event "Write it, Do it", which means that you have to interpret your event partner's written description of an object and replicate the object based on the description. Unfortunately, your partner is bad at spelling and misspelled a critical word in the description. Your task is to figure out which word your partner most likely meant to write.

The first line of input contains a string s: the word misspelled by your partner. Assume that your partner did not add or remove any letters; they only replaced letters with incorrect ones. The next line contains a single positive integer n indicating the number of possible valid words that your partner could have meant to write. Each of the next n lines contains each of these words. There is guaranteed to be at least one word of the same length as the misspelled word.

Output a single word w: the word in the dictionary of possible words closest to the misspelled word. "Closeness" is defined as the minimum number of different characters. If there is a tie, choose the word that comes first in the given dictionary of words.

deat
6
fate
feet
beat
meat
deer
dean

beat