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
        w_l = len(word_to_find)
        word_len = len(word)
        if w_l > word_len:
            res+="0\n"
            continue

        while k < word_len:
            if word_len+1-i < w_l:
                break

            if k-i >= w_l-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()