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