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ţă
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 cuvinte1.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, Lcuvâ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 Li-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 cuvinte1.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
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).