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.append(0)
    else:
        slovo = slovo.replace(text, " ")
        result.append(1)

print(result)