n,q = map(int,input().split(" "))
slovo = str(input())
pomocna = 0
result = ""
for i in range(q):
    cislo_index = int(input())
    text = str(input())
    while True:
        if slovo[pomocna:cislo_index] == text:
            slovo = (slovo.replace(slovo[pomocna:cislo_index],""))
            result += "1\n"
            pomocna = 0
            break
        else:
            pomocna += 1
            cislo_index += 1
        if cislo_index > len(slovo):
            pomocna = 0
            result += "0\n"
            break
    pomocna = 0
print(result)