Prologin, the French National Computer Science Contest

Énoncé¶

Dans le cadre de vos études d'apprenti jedi, vous devez accomplir votre premier stage. Vous avez donc décidé de rejoindre les facteurs galactiques. Vous vous occupez ainsi de livrer les lettres et colis aux habitants des différentes planètes du système stellaire. Le problème étant que vos collègues ne sont pas très doués en orthographe et ils ont malencontreusement glissé quelques fautes dans les noms notés sur les colis.

Ayant devant vous une série de boîtes aux lettres ainsi que le nom de famille erroné noté sur le colis, écrivez un algorithme qui permet de retrouver le nom original parmi ceux affichés sur les boîtes aux lettres.

On part du principe que vous ne vous êtes pas trompé d'immeuble donc la solution existe et est unique.

Une faute représente la substitution d'une lettre par une autre (il n'y a ni ajout ni suppression de lettre), le nom noté sur le colis peut contenir de 1 à 3 fautes et tous les noms de la liste de boîtes aux lettres sont au format "NOM" (composé de 4 à 10 lettres, uniquement minuscules).

Entrée¶

Sur la première ligne, la chaîne de caractère NOM correspond au nom erroné noté sur le colis.
Sur la deuxième ligne, l'entier $N$ correspondant au nombre de boîtes aux lettres.
Sur les $N$ lignes suivantes, les noms de familles.

Sortie¶

Le nom corrigé tel qu'il est affiché sur la boîte aux lettres.

Contraintes¶

$1 ≤ N ≤ 100$

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

rochard
8
martin
bernard
thomas
petit
robert
richard
durand
dubois

Sample output

richard

Note

Le nom "richard" est l'unique nom de famille ayant une substitution de différence avec le nom "rochard".