N, Q = map(int, input().split())
slovo = str(input())
result = []
for _ in range(Q):
    int(input())
    word = str(input())
    if word not in slovo:
        result.append(0)
    else:
        slovo = slovo.replace(word, "")
        result.append(1)
for i in result:
    print(i)