cuvinte

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 cuvinte.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 cuvinte.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) < $10 \ 001$
• 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

cuvinte.in

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

cuvinte.out

0
1
0
1
0
1