def main():
    l1 = input()
    _, burners_num = l1.split(" ")
    burners_num = int(burners_num)
    word = input()

    word = word.strip()

    res = ""
    for i in range(burners_num):
        input()
        word_to_find = input()

        i =0
        flag = False
        k=0
        if len(word_to_find) > len(word):
            res+="0\n"
            continue

        while k < len(word):
            if len(word)+1-i < len(word_to_find):
                break
                
            if k-i >= len(word_to_find)-1:
                res+="1\n"
                word = word[:i]+word[k+1:]

                flag = True
                break
            if word_to_find[k-i] != word[k]:
                i=k

            k+=1

        if not flag:
            res+="0\n"

    res = res.strip("\n")
    print(res)

main()