Županijsko natjecanje 2016. / Osnovna škola (8. razred) - 3. zadatak

Zrinka uči tipkati bez gledanja u tipkovnicu i zato ponekad pritisne pogrešnu tipku.

Ona koristi standardnu englesku tipkovnicu (najpogodniju za programiranje) čiji je raspored slova prikazan na slici1 :

Zrinka griješi samo na način da ponekad umjesto traženog slova pritisne njemu susjedno slovo (susjedna slova su ona čiji se rubovi na slici dodiruju, npr. H i U susjedna su slova, ali K i U nisu susjedna).

Na primjer, moguće da umjesto riječi PROGRAM Zrinka napiše PTIGTAN.

Poznata ti je riječ koju je Zrinka napisala, a tvoj je zadatak pronaći riječ koju je Zrinka htjela napisati.

Da bi zadatak bio lakši, zadan je i popis riječi među kojima se nalazi tražena riječ.

ULAZNI PODATCI

U prvom retku nalazi se riječ sastavljena od barem 2, a najviše 26 velikih slova engleske abecede: riječ koju je Zrinka napisala.

U sljedećem retku nalazi se prirodan broj N (2 ≤ N ≤ 15), broj riječi na popisu.

U svakom od sljedećih N redaka nalazi se riječ s popisa sastavljena od barem 2, a najviše 26 velikih slova engleske abecede.

Riječi u svim redcima međusobno su različite.

IZLAZNI PODATCI

U jedan redak ispiši riječ iz popisa koju je Zrinka htjela napisati.

Ako ima više mogućih riječi, ispiši ih jednu ispod druge, abecednim redom.

Test podaci bit će takvi da će odgovarajuća riječ uvijek biti na popisu.

PRIMJERI TEST PODATAKA

Ulaz

PTIGTAN
2
PROGRAM
TRISTAN

Izlaz

PROGRAM

Ulaz

JOD
7
HOD
IKS
KOD
MIR
MIX
OPS
UPS

Izlaz

HOD
IKS
KOD
MIR
MIX
UPS