Utalentowany 小A został wybrany na autora zadań ION2018. Teraz musi rozwiązać problem nadawania im nazw.
小A został wybrany na autora zadań ION2018. Starannie przygotował zadanie bardzo wysokiej jakości i wykonał już całą pracę poza nadaniem mu nazwy.
Ponieważ ION odbywa się już od wielu lat, istnieją również zasady nadawania nazw zadaniom. Podręcznik autorów ION stanowi: każdego roku komisja zadaniowa ustala napis złożony z małych liter, zwany napisem nazw dla danego roku. Nazwa każdego zadania musi być niepustym spójnym podnapisem napisu nazw dla tego roku i nie może być taka sama jak nazwa żadnego zadania z poprzedniego roku.
Z pewnych szczególnych powodów 小A nie zna nazw poszczególnych zadań ION2017, ale w pewien szczególny sposób zdobył napis nazw ION2017. Teraz 小A ma $Q$ zapytań: w każdym z nich podane są napisy nazw ION2017 oraz ION2018. Należy obliczyć, ile nazw zadania z pewnością spełnia zasady komisji, czyli jest niepustym spójnym podnapisem napisu nazw ION2018 i na pewno nie jest nazwą żadnego zadania ION2017.
Z pewnych szczególnych powodów napisy nazw ION2017 podawane we wszystkich zapytaniach są spójnymi podnapisami pewnego napisu. Szczegóły opisano w formacie wejścia.
Wejście
Pierwszy wiersz zawiera napis $S$. Napisy nazw ION2017 podawane w kolejnych zapytaniach są spójnymi podnapisami $S$.
Drugi wiersz zawiera dodatnią liczbę całkowitą $Q$, oznaczającą liczbę zapytań.
Każdy z kolejnych $Q$ wierszy zawiera napis $T$ oraz dwie dodatnie liczby całkowite $l,r$. Zapytanie dotyczy liczby nazw, które z pewnością spełniają zasady, jeśli napis nazw ION2017 to $S[l..r]$, a napis nazw ION2018 to $T$.
Wszystkie napisy podane na wejściu składają się z małych liter.
Wyjście
Wypisz $Q$ wierszy. W $i$-tym wierszu wypisz jedną nieujemną liczbę całkowitą, będącą odpowiedzią na $i$-te zapytanie.
Przykład
Wejście 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Wyjście 1
12 10 4
Przykład 2
Zobacz pliki name/name2.in oraz name/name2.ans w katalogu zawodnika.
Podzadania
| Test | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Ograniczenia zapytań | Pozostałe ograniczenia |
|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 2 | $1000$ | $200$ | $40000$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 3 | $1000$ | $200$ | $40000$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 4 | $1000$ | $200$ | $5\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 5 | $1000$ | $200$ | $5\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 6 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 7 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 8 | $10^5$ | $10^5$ | $2\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 9 | $10^5$ | $10^5$ | $2\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Napisy losowe |
| 10 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 11 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Napisy losowe |
| 12 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 13 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Napisy losowe |
| 14 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 15 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Napisy losowe |
| 16 | $5\cdot10^5$ | $10^5$ | $10^6$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Brak |
| 17 | $5\cdot10^5$ | $10^5$ | $10^6$ | Dla wszystkich zapytań $l=1,r=\lvert S\rvert$ | Napisy losowe |
| 18 | $2\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 19 | $3\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 20 | $4\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 21 | $5\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 22 | $5\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 23 | $5\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 24 | $5\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
| 25 | $5\cdot10^5$ | $10^5$ | $10^6$ | Brak | Brak |
Dla wszystkich danych zachodzi $1\le l\le r\le\lvert S\rvert$ oraz $1\le\lvert T\rvert\le5\cdot10^5$.