#include <bits/stdc++.h>
using namespace std;


ifstream fin("cuvinte8.in");
ofstream fout("cuvinte8.out");
int n, k;
int dp[2][10005];
string wrong,cuv;

int main()
{
    int lenwr, lenac;
    fin >> n >> k;
    fin >> lenwr >>wrong ;
    for (int i = 1; i <= n; i++)
    {
        fin >> lenac >> cuv;
        bool lin = false;
        for (int i = 0; i <= 10001; i++)
            dp[0][i] = 0;
        for (int j = 0; j <= lenac; j++)
            dp[1][j] = j;
        int x;

        for (int i = 1; i <= lenwr; i++) {
            dp[lin][0] = i;
            int mx = max(1 ,i - 2 * k), mn = min(lenac,i + 2 *k);
            for (int j = mx; j <=mn; j++)
            {
                x = 1;
                if (wrong[i - 1] == cuv[j - 1])
                    x = 0;
                dp[lin][j] = min({ 1 + dp[!lin][j], 1 + dp[lin][j - 1], x + dp[!lin][j - 1] });
            }
            lin = !lin;
        }
        if (dp[!lin][lenac] <= k)
            fout << "1\n";
        else fout << "0\n";

    }
    fin.close();
    fout.close();
    return 0;
}