#include <iostream>
#include <cstring>

int main() {
    size_t N, Q;
    std::cin >> N >> Q;
    char* word = (char*)malloc(N + 1);
    char* subStr = (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;
        subStr[size_of_word] = '\0';
        scanf ("%s", subStr);

        char* subStrInWord;
        if(word != nullptr)
            subStrInWord = strstr(word, subStr);

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

        int addrShift = subStrInWord - word;
        memcpy(word + addrShift, word + addrShift + size_of_word, N - size_of_word - addrShift);
        N -= size_of_word;
        word[N] = '\0';
        subStr[size_of_word] = '\n';
    }
    free(word);
    free(subStr);
    return 0;
}