Masala #KWNATCLU5Y

Xotira 128 MB Vaqt 2000 ms
14

So'zlarni topish

Ali va Vali so'z o'yinini o'ynashmoqda. Ali bir harf aytadi, Vali esa o'sha harf bilan boshlanadigan so'zni aytadi. Biroq, so'z ruxsat etilgan so'zlar ro'yxati ichida bo'lishi kerak va Vali uni eng kam marta aytgan bo'lishi kerak. Agar bir nechta variant mavjud bo'lsa, Vali leksikografik eng kichigini tanlaydi. Har bir Ali tomonidan aytilgan harf uchun, Vali so'z topa oladi.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita musbat butun sonlar K va N berilgan. Keyingi K qatorda kichik lotin harflaridan iborat, uzunligi 21 ta belgidan oshmaydigan so'zlar beriladi. Keyingi N qatorning har birida kichik lotin harflaridan iborat bitta harf keltiriladi.

\(1 \le K, N \le 10^5\)


Chiquvchi ma'lumotlar:

Siz N qatorda, har birida shartga mos keladigan bitta so'zni chop etishingiz kerak.


Misollar
# input.txt output.txt
1
4 5
toshkent
samarqand
sirdaryo
termiz
t
s
s
t
t
termiz
samarqand
sirdaryo
toshkent
termiz
2
5 3
andijon
fargona
qarshi
termiz
urganch
q
f
a
qarshi
fargona
andijon
3
1 3
xorazm
x
x
x
xorazm
xorazm
xorazm