Balaurul Arhirel se decide să înveţe biologie, aşa că doreşte să cumpere manualul de clasa a X-a. Din păcate, acesta nu se mai găsește pe piaţă, dar Balaurul reuşeşte să găsească o copie la un prieten. După ce începe să citească, Balaurul Arhirel observă că există greşeli în copia prietenului, iar într-un impuls de energie, se hotărăşte să corecteze manualul. El are la dispoziţie un dicţionar de M cuvinte dintre care trebuie să extragă variante pentru cuvântul greşit. Asupra cuvântului greşit balaurul poate să facă următoarele schimbări în așa fel încât acesta să ajungă la o variantă din dicționar:
– poate șterge o literă;
– poate insera o literă;
– poate schimba o literă în altă literă.
Totuși, Balaurul Arhirel este leneş, aşa că nu doreşte să opereze mai mult de K schimbări în cuvântul greșit pentru a-l aduce la o formă corectă (existentă în dicționar).

Cerința

Ajutaţi-l pe Balaurul Arhirel să afle care dintre cuvintele din dicţionar ar putea fi variante ale cuvântului greşit.

Date de intrare

Fișierul de intrare cuvinte8.in conţine pe prima linie cele două numere M şi K, separate printr-un spaţiu, reprezentând numărul de cuvinte din dicţionar şi numărul maxim de modificări ce pot fi efectuate asupra cuvântului ce trebuie corectat. Pe a doua linie se găsesc separate printr-un spaţiu lungimea cuvântului greşit, L[cuvânt], şi cuvântul greşit. Pe următoarele M linii se găsesc cuvintele din dicţionar, câte un cuvânt pe o linie în forma următoare: pe linia i lungimea L[i-2] a cuvântului i-2, separată printr-un singur spaţiu de cuvântul i-2.

Date de ieșire

Fișierul de ieșire cuvinte8.out va conţine M linii. Pe linia i se află valoarea 1 pentru cazul în care cuvântul i din dicţionar este o variantă pentru cuvântul greşit dat, respectiv valoarea 0 în caz contrar.

Restricții și precizări

• 0 < M < 21
• 0 < K < 31
• 0 < lungimea oricărui cuvânt (inclusiv cel greșit) < 10001
• Cuvintele sunt formate doar din literele alfabetului latin, iar literele mici diferă de cele mari (de exemplu, Z nu este acelaşi lucru cu z).

Exemplu:

cuvinte8.in

6 2
6 radiux
5 ladin
6 Radius
6 ridica
5 radio
6 adipos
5 cadiu

cuvinte8.out

0
1
0
1
0
1