Boîtes aux lettres – Regional event 2020

Level 2

É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".

Sample input
garriet
11
rousseau
vincent
muller
lefevre
faure
andre
mercier
blanc
guerin
boyer
garnier
Sample output
garnier
Note

Le nom "garnier" est l'unique nom de famille ayant deux substitutions de différence avec le nom "garriet".

Submit your solution

You have to register or log in to be able to submit your solution.