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