M, Q = list(map(int, input("").split()))
line = input()

words = []
for _ in range(Q):
    _ = input()
    words.append(input())

for word in words:
    # print(line)
    start = line.find(word)
    if start == -1:
        print(0)
        continue
    else:
        print(1)
    line = line[:start] + line[start+len(word):]