n,q = map(int,input().split(" "))
slovo = str(input())
"""s = int(input())
print(slovo[0:s])
print(slovo[1:s+1])
print(slovo[2:s+2])"""
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.append(1)
            pomocna = 0
            break
        else:
            pomocna += 1
            cislo_index += 1
        if cislo_index > len(slovo):
            pomocna = 0
            result.append(0)
            break
    pomocna = 0


for i in range(len(result)):
    print(result[i])