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 cuz
).
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