Le très talentueux 小 A a été choisi pour concevoir les problèmes d'ION2018. Il doit maintenant résoudre la question de leur nom.
Énoncé
小 A a été choisi pour concevoir les problèmes d'ION2018. Il a soigneusement préparé un problème de très grande qualité et a terminé tout le travail, à l'exception du choix de son nom.
Comme ION a déjà connu de nombreuses éditions, le choix des noms des problèmes est lui aussi réglementé. Le manuel de conception des problèmes d'ION stipule que, chaque année, le comité de conception fixe une chaîne de lettres minuscules, appelée la chaîne de dénomination de cette année. Le nom de chaque problème doit être une sous-chaîne contiguë non vide de la chaîne de dénomination de cette année et ne doit être identique au nom d'aucun problème de l'année précédente.
Pour certaines raisons particulières, 小 A ne connaît pas les noms des problèmes d'ION2017, mais il a obtenu par des moyens particuliers la chaîne de dénomination d'ION2017. 小 A a maintenant $Q$ requêtes : pour chacune, étant données la chaîne de dénomination d'ION2017 et celle d'ION2018, déterminer combien de noms de problème respectent à coup sûr les règles du comité. Autrement dit, le nom doit être une sous-chaîne contiguë non vide de la chaîne de dénomination d'ION2018 et être à coup sûr différent du nom de chacun des problèmes d'ION2017.
Pour certaines raisons particulières, les chaînes de dénomination d'ION2017 données dans toutes les requêtes sont des sous-chaînes contiguës d'une même chaîne ; les détails figurent dans le format d'entrée.
Entrée
La première ligne contient une chaîne $S$. Les chaînes de dénomination d'ION2017 données dans les requêtes qui suivent sont toutes des sous-chaînes contiguës de $S$.
La deuxième ligne contient un entier strictement positif $Q$, le nombre de requêtes.
Chacune des $Q$ lignes suivantes contient une chaîne $T$ et deux entiers strictement positifs $l,r$. Elle demande combien de noms respectent à coup sûr les règles lorsque la chaîne de dénomination d'ION2017 est $S[l..r]$ et celle d'ION2018 est $T$.
Toutes les chaînes données en entrée sont constituées de lettres minuscules.
Sortie
Afficher $Q$ lignes. La $i$-ème ligne contient un entier positif ou nul représentant la réponse à la $i$-ème requête.
Exemples
Entrée 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Sortie 1
12 10 4
Exemple 2
Voir les fichiers name/name2.in et name/name2.ans dans le répertoire des candidats.
Sous-tâches
| Test | $\lvert S\rvert \le$ | $Q \le$ | $\sum \lvert T\rvert \le$ | Restrictions sur les requêtes | Autres restrictions |
|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| 2 | $1000$ | $200$ | $40000$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| 3 | $1000$ | $200$ | $40000$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert \le 200$ |
| 4 | $1000$ | $200$ | $5 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 5 | $1000$ | $200$ | $5 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 6 | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 7 | $5 \times 10^5$ | $1$ | $5 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 8 | $10^5$ | $10^5$ | $2 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 9 | $10^5$ | $10^5$ | $2 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Chaînes aléatoires |
| 10 | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 11 | $2 \times 10^5$ | $10^5$ | $4 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Chaînes aléatoires |
| 12 | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 13 | $3 \times 10^5$ | $10^5$ | $6 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Chaînes aléatoires |
| 14 | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 15 | $4 \times 10^5$ | $10^5$ | $8 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Chaînes aléatoires |
| 16 | $5 \times 10^5$ | $10^5$ | $8 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Aucune |
| 17 | $5 \times 10^5$ | $10^5$ | $8 \times 10^5$ | Pour toutes les requêtes, $l=1,r=\lvert S\rvert$ | Chaînes aléatoires |
| 18 | $2 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 19 | $3 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 20 | $4 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 21 | $5 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 22 | $5 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 23 | $5 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 24 | $5 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
| 25 | $5 \times 10^5$ | $10^5$ | $10^6$ | Aucune | Aucune |
Pour toutes les données, $1 \le l \le r \le |S|$ et $1 \le |T| \le 5 \times 10^5$.