radio

Cerință

Laura a dezvoltat recent o pasiune pentru şirurile de caractere generate aleator. Ca să o ajute să treacă mai uşor peste sesiune, prietenii ei s-au gândit să o înveselească şi i-au cumpărat un astfel de şir de lungime $N$, conţinând doar litere mici ale alfabetului englez.

De dimineaţă, Laura a început să asculte muzică la radio şi a auzit $M$ cuvinte, toate având aceeaşi lungime $L$, care i-au plăcut foarte mult. Aceste cuvinte sunt formate tot din litere mici ale alfabetului englez. Acum ea şi-ar dori să vadă, pentru fiecare cuvânt, dacă acesta apare ca subsecvență în şirul primit cadou. Cum cuvintele sunt destul de lungi, Laura nu este sigură că le-a auzit corect, dar este convinsă că nu a înţeles greşit mai mult de $K$ litere din fiecare cuvânt.

Aşadar, voi trebuie să îi spuneţi, pentru fiecare din cele $M$ cuvinte, dacă există o subsecvenţă de lungime $L$ în şirul primit cadou astfel încât cuvântul şi subsecvenţa să difere în cel mult $K$ poziţii.

Date de intrare

Pe prima linie a fişierului de intrare radio.in se află $4$ numere întregi $N \ M \ L \ K$, având semnificaţia din enunţ. Pe următoarea linie, se află $N$ caractere neseparate prin spaţii ce reprezintă şirul primit cadou de fată. Pe următoarele $M$ linii, se află câte $L$ caractere neseparate prin spaţii, ce reprezintă cuvintele pe care Laura le-a auzit la radio (aşa cum le-a înţeles ea).

Date de ieșire

În fişierul de ieşire radio.out va conţine $M$ linii. Pe linia $i$, veţi afişa $1$ dacă există o subsecvenţă în şirul primit cadou de fată care să difere în cel mult de $K$ poziţii de al $i$-lea cuvânt din fişierul de intrare, respectiv $0$, în caz contrar.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq M \leq 500$
• $1 \leq K \leq 50$
• $500 \leq L \leq 2 \ 500$
• Printr-un şir de litere {a - z} generat aleator se înţelege un şir în care pe fiecare poziţie, oricare dintre literele {a - z} are aceeaşi probabilitate de apariţie.
• Pentru $10\%$ din teste, $N \leq 10 \ 000$.
• Pentru $30\%$ din teste, $N \leq 100 \ 000$.
• Pentru alte $10\%$ din teste, $K = 0$.
• Toate testele vor respecta condiţia $500 \leq L \leq 2 \ 500$. Exemplul de mai jos nu respectă această restricţie şi nici nu este generat aleator, deoarece are ca scop înţelegerea enunţului.

Exemplu

radio.in

10 3 6 2
anaaremere
roaane
aareme
renere

radio.out

0
1
1

Explicație

Pentru cuvântul roaane nu există nici o subsecvență în anaaremere astfel încât cuvântul şi subsecvenţa să difere în mai mult de $2$ poziţii. Cuvântul aareme apare exact în şirul dat, iar pentru renere există subsecvenţa remere faţă de care diferă printr-o singură poziţie.