Zig i Zag igraju igru s riječima. Zig kaže jedno slovo, a Zag izgovori riječ koja počinje tim slovom. Pri tome izgovorena riječ mora biti s popisa dozvoljenih riječi i takva da ju je Zag do tada izgovorio najmanje puta. Ako izbor riječi nije jednoznačan tada će Zag odabrati onu koja je leksikografski manja (prije po abecedi). Za svako Zigovo slovo bit će moguće odabrati riječ. Neka je zadan popis od točno K različitih dozvoljenih riječi te niz od N slova koje je Zig zadao. Napišite program koji će na osnovu ulaznih podataka ispisati niz od N riječi koje je Zag izgovorio tijekom igre

Ulazni podaci

U prvom retku nalaze se prirodni brojevi K (1 ≤ K ≤ 100 000) i N (1 ≤ N ≤ 100 000) iz teksta zadatka. U sljedećih K redaka nalazi se po jedna riječ sastavljena od malih slova engleske abecede ne dulja od 21 znaka. U sljedećih N redaka nalazi se po jedno malo slovo engleske abecede.

Izlazni podaci

U N redaka treba ispisati po jednu riječ iz teksta zadatka.

Primjeri test podataka

Ulaz

4 5
zagreb
split
zadar
sisak
z
s
s
z
z

Izlaz

zadar
sisak
split
zagreb
zadar

Ulaz

5 3
london
rim
pariz
moskva
sarajevo
p
r
p

Izlaz

pariz
rim
pariz

Ulaz

1 3
zagreb
z
z
z

Izlaz

zagreb
zagreb
zagreb