Задача C. Длинный текст и много слов

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными. Обратите внимание, данная задача отличается от задачи B только ограничениями.

Формат входного файла

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

Формат выходного файла

В выходном файле должны содержаться N чисел 1 или 0, обозначающих, что соответствующее слово входит или не входит в текст.

Ограничения

1 ≤ L ≤ 20000, 1 ≤ N ≤ 10000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
Longlongstring
2
short
string
0 1

0.099s 0.043s 13