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

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

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