Задача №114134. Суровый корректор
По мнению Александра Павловича, текст необычайно красив, если некоторые особые слова (например, «коммунизм», «Ленин», «счастье») встречаются не слишком часто, но и не слишком редко, к тому же достаточно равномерно.
Александр Павлович работает корректором. К нему поступают тексты, он имеет право их некоторым образом менять, после чего возвращает уже исправленную версию.
В связи со своими воззрениями о красоте Александру Павловичу постоянно приходится проверять, сколько особых слов сейчас в той или иной части текста.
Он настолько устал от рутинного подсчёта: «а сколько тут особых слов?», «а сколько тут?», что просит вас помочь ему автоматизировать этот процесс.
Первая строка входного файла содержит текст длины \(L\) (\(1 \leq L \leq 10^5\)), в котором ищутся особые слова.
Следующая строка содержит \(N\) (\(1 \le n \le 10^5\)) — количество особых слов.
Следующие \(n\) строк содержат особые слова. Все особые слова различны. Суммарная длина строк не превосходит \(10^5\).
В следующей строке дано \(Q\) (\(1 \le q \le 10^5\)) — количество интересных Александру Павловичу отрезков.
Следующие \(q\) строк содержат сами отрезки.
Выведите \(q\) чисел — количества вхождений особых слов в соответствующий отрезок текста.
Тесты к данной задаче состоят из семи групп тестов. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов зависимых групп и теста из условия.
Обозначим за \(LEN_{max}\) максимальную длину особого слова.
- \(n \leq 1000, q = 1\), группа оценивается в \(11\) баллов.
- \(LEN_{max} \leq 1000, q = 1\), группа оценивается в \(13\) баллов.
- \(q = 1\), группа оценивается в \(12\) баллов. Группа зависит от 1, 2.
- \(n \leq 1000, q \leq 10000\), группа оценивается в \(21\) балл. Группа зависит от 1.
- \(LEN_{max} \leq 1000, q \leq 10000\), группа оценивается в \(19\) баллов. Группа зависит от 2.
- \(q \leq 10000\), группа оценивается в \(23\) балла. Группа зависит от 1, 2, 3, 4, 5.
- полные ограничения, группа оценивается в \(1\) балл. Группа зависит от 1, 2, 3, 4, 5, 6.
abacababa 2 a aba 3 5 9 2 2 2 6
5 0 2