Contexto. El talentoso 小 A ha sido elegido como autor de problemas de ION2018 y ahora necesita resolver cómo nombrar su problema.
Descripción
小 A ha sido elegido como autor de problemas de ION2018. Ha preparado cuidadosamente un problema de gran calidad y ha terminado todo el trabajo salvo ponerle un nombre.
Como ION ya se ha celebrado muchas veces, también hay normas para los nombres de los problemas. El manual de preparación de ION establece que cada año el comité de problemas elige una cadena de letras minúsculas, llamada cadena de nombres de ese año. El nombre de cada problema debe ser una subcadena contigua no vacía de la cadena de nombres de ese año, y no puede coincidir con el nombre de ningún problema del año anterior.
Por ciertas razones especiales, 小 A no conoce los nombres de los problemas de ION2017, pero ha conseguido su cadena de nombres por medios especiales. Ahora tiene $Q$ consultas: en cada una se dan las cadenas de nombres de ION2017 e ION2018, y hay que contar cuántos nombres de problemas cumplen con certeza las normas del comité. Es decir, deben ser subcadenas contiguas no vacías de la cadena de nombres de ION2018 y estar seguros de no coincidir con el nombre de ningún problema de ION2017.
Por ciertas razones especiales, las cadenas de nombres de ION2017 de todas las consultas son subcadenas contiguas de una misma cadena. Consulta los detalles en el formato de entrada.
Entrada
La primera línea contiene una cadena $S$. Las cadenas de nombres de ION2017 de las consultas posteriores son subcadenas contiguas de $S$.
La segunda línea contiene un entero positivo $Q$, el número de consultas.
Cada una de las siguientes $Q$ líneas contiene una cadena $T$ y dos enteros positivos $l,r$. La consulta pregunta cuántos nombres cumplen con certeza las normas si la cadena de nombres de ION2017 es $S[l..r]$ y la de ION2018 es $T$.
Se garantiza que todas las cadenas de la entrada contienen únicamente letras minúsculas.
Salida
Escribe $Q$ líneas. La línea $i$ debe contener un entero no negativo: la respuesta a la consulta $i$.
Ejemplos
Entrada 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Salida 1
12 10 4
Ejemplo 2
Consulta name/name2.in y name/name2.ans en el directorio de los participantes.
Subtareas
| Caso de prueba | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Restricciones de las consultas | Otras restricciones |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | Para todas las consultas, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $2$ | $1000$ | ||||
| $3$ | |||||
| $4$ | $5\times10^5$ | Ninguna | |||
| $5$ | |||||
| $6$ | $5\times10^5$ | $1$ | |||
| $7$ | |||||
| $8$ | $10^5$ | $10^5$ | $2\times10^5$ | ||
| $9$ | Cadenas aleatorias | ||||
| $10$ | $2\times10^5$ | $4\times10^5$ | Ninguna | ||
| $11$ | Cadenas aleatorias | ||||
| $12$ | $3\times10^5$ | $6\times10^5$ | Ninguna | ||
| $13$ | Cadenas aleatorias | ||||
| $14$ | $4\times10^5$ | $8\times10^5$ | Ninguna | ||
| $15$ | Cadenas aleatorias | ||||
| $16$ | $5\times10^5$ | $10^6$ | Ninguna | ||
| $17$ | Cadenas aleatorias | ||||
| $18$ | $2\times10^5$ | Ninguna | Ninguna | ||
| $19$ | $3\times10^5$ | ||||
| $20$ | $4\times10^5$ | ||||
| $21$ | $5\times10^5$ | ||||
| $22$ | |||||
| $23$ | |||||
| $24$ | |||||
| $25$ |
Para todos los datos, se garantiza que $1\le l\le r\le|S|$ y $1\le|T|\le5\times10^5$.