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