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

    word = word.strip()

    res = ""
    for i in range(letters_num):
        w_len = input()
        word_to_find = input()
        w_len = int(w_len)
        i =0
        flag = False
        k=0

        w_word_to_find = len(word_to_find)
        if w_word_to_find > w_len:
            res+="0\n"
            continue

        while k < w_len:
            if w_len+1-i < w_word_to_find:
                break

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