Prologin, le concours national d'informatique

É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$

Contraintes d'exécution

Utilisation mémoire maximum: 1000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

rochard
8
martin
bernard
thomas
petit
robert
richard
durand
dubois

Exemple de sortie

richard

Commentaire

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