n,q = map(int,input().split(" "))
slovo = str(input())
result = ""
for _ in range(q):
    cislo_index = int(input())
    text = str(input())
    if text not in slovo:
        result += "0\n"
    else:
        result += "1\n"
        idx = slovo.find(text)
        slovo = slovo[:idx] + slovo[idx+len(text):]
print(result)