Талантливый 小 A был выбран автором задач ION2018. Теперь ему нужно решить вопрос с названием задачи.
Условие задачи
小 A был выбран автором задач ION2018. Он тщательно подготовил задачу очень высокого качества и уже выполнил всю работу, кроме выбора названия.
ION проводится уже много лет, поэтому существуют и правила именования задач. Согласно руководству для авторов ION, каждый год жюри задаёт строку из строчных букв, которую мы называем строкой названий этого года. Название каждой задачи должно быть непустой непрерывной подстрокой строки названий этого года и не должно совпадать с названием ни одной задачи предыдущего года.
По некоторым особым причинам 小 A не знает названий задач ION2017, но особыми способами ему удалось получить строку названий ION2017. Теперь у 小 A есть $Q$ запросов: в каждом даны строка названий ION2017 и строка названий ION2018. Требуется найти количество различных названий задачи, которые гарантированно удовлетворяют требованиям жюри: являются непустыми непрерывными подстроками строки названий ION2018 и гарантированно не совпадают с названием ни одной задачи ION2017.
По некоторым особым причинам строки названий ION2017 во всех запросах являются непрерывными подстроками некоторой строки. Подробности приведены в разделе «Входные данные».
Входные данные
В первой строке дана строка $S$. Строки названий ION2017 во всех последующих запросах являются непрерывными подстроками $S$.
Во второй строке дано положительное целое число $Q$ — количество запросов.
В каждой из следующих $Q$ строк даны строка $T$ и два положительных целых числа $l,r$. Требуется найти количество названий, гарантированно удовлетворяющих правилам, если строка названий ION2017 равна $S[l..r]$, а строка названий ION2018 равна $T$.
Гарантируется, что все строки во входных данных состоят из строчных букв.
Выходные данные
Выведите $Q$ строк. В $i$-й строке выведите неотрицательное целое число — ответ на $i$-й запрос.
Примеры
Входные данные 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Выходные данные 1
12 10 4
Пример 2
См. файлы name/name2.in и name/name2.ans в каталоге участника.
Подзадачи
| Тест | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Ограничения на запросы | Другие ограничения |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | Для всех запросов $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $2$ | $1000$ | $200$ | $40000$ | Для всех запросов $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $3$ | $1000$ | $200$ | $40000$ | Для всех запросов $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $4$ | $1000$ | $200$ | $5\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $5$ | $1000$ | $200$ | $5\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $6$ | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $7$ | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $8$ | $10^5$ | $10^5$ | $2\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $9$ | $10^5$ | $10^5$ | $2\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Случайные строки |
| $10$ | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $11$ | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Случайные строки |
| $12$ | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $13$ | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Случайные строки |
| $14$ | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $15$ | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Случайные строки |
| $16$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Нет |
| $17$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Для всех запросов $l=1,r=\lvert S\rvert$ | Случайные строки |
| $18$ | $2\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $19$ | $3\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $20$ | $4\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $21$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $22$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $23$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $24$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
| $25$ | $5\cdot10^5$ | $10^5$ | $10^6$ | Нет | Нет |
Для всех данных гарантируется $1\le l\le r\le\lvert S\rvert$, $1\le\lvert T\rvert\le5\cdot10^5$.