#include <iostream>
#include <cstring>

int main() {
    size_t N, Q;
    std::cin >> N >> Q;
    char* word = (char*)malloc(N + 1);
    word[N] = '\0';
    scanf ("%s", word);
    for(size_t i = 0; i < Q; i ++){
        size_t size_of_word;
        std::cin >> size_of_word;
        char* substr = (char*)malloc(size_of_word + 1);
        substr[size_of_word] = '\0';
        scanf ("%s", substr);
        char* subStrInWord = strstr(word, substr);

        if(subStrInWord == nullptr){
            std::cout << "0\n";
            free(substr);
            continue;
        }
        std::cout << "1\n";

        char* newStr = (char*) malloc(N - size_of_word + 1);
        newStr[N-size_of_word] = '\0';

        int addrShift = subStrInWord - word;
        memcpy(newStr, word, addrShift);
        memcpy(newStr + addrShift, word + addrShift + size_of_word, N - size_of_word - addrShift);
        N -= size_of_word;
        free(word);
        free(substr);
        word = newStr;
    }
    free(word);
    return 0;
}