Талановитого 小 A обрали автором задач ION2018. Тепер йому потрібно розв'язати питання назви задачі.
Умова задачі
小 A обрали автором задач ION2018. Він ретельно підготував дуже якісну задачу та вже виконав усю роботу, крім вибору назви.
Оскільки ION проводиться вже багато років, назви задач також підпорядковуються правилам. Посібник авторів ION встановлює: щороку комітет задає рядок з малих латинських літер, який називається рядком найменування цього року. Назва кожної задачі має бути непорожнім суцільним підрядком рядка найменування відповідного року та не повинна збігатися з назвою жодної задачі попереднього року.
З певних причин 小 A не знає назв задач ION2017, проте особливими засобами отримав рядок найменування ION2017. Тепер він має $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\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $5$ | $5\times10^5$ | $200$ | $5\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $6$ | $5\times10^5$ | $1$ | $5\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $7$ | $5\times10^5$ | $1$ | $5\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $8$ | $10^5$ | $10^5$ | $2\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $9$ | $10^5$ | $10^5$ | $2\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Випадкові рядки |
| $10$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $11$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Випадкові рядки |
| $12$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $13$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Випадкові рядки |
| $14$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $15$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Випадкові рядки |
| $16$ | $5\times10^5$ | $10^5$ | $10^6$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Немає |
| $17$ | $5\times10^5$ | $10^5$ | $10^6$ | Для всіх запитів $l=1,r=\lvert S\rvert$ | Випадкові рядки |
| $18$ | $2\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $19$ | $3\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $20$ | $4\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $21$ | $5\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $22$ | $5\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $23$ | $5\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $24$ | $5\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
| $25$ | $5\times10^5$ | $10^5$ | $10^6$ | Немає | Немає |
Для всіх даних гарантовано $1\le l\le r\le\lvert S\rvert$, $1\le\lvert T\rvert\le5\times10^5$.