小 Y est un étudiant qui étudie récemment des problèmes portant sur les chaînes de caractères.
小 Y a découvert les définitions suivantes :
- Pour une chaîne $s[1:n]$ de longueur $n$, sa sous-chaîne $s[l:r]$ ($1\le l\le r\le n$) est la nouvelle chaîne obtenue en concaténant dans l’ordre $s[l],s[l+1],\ldots,s[r]$.
- Pour une chaîne $s[1:n]$ de longueur $n$, son renversement $R(s)$ est la chaîne obtenue en concaténant dans l’ordre $s[n],s[n-1],\ldots,s[1]$, c’est-à-dire en inversant l’ordre des caractères.
- Pour deux chaînes $a[1:n],b[1:n]$ de même longueur $n$, on dit que $a$ est strictement inférieure à $b$ dans l’ordre lexicographique si et seulement s’il existe $1\le i\le n$ tel que, pour tout $1\le j<i$, $a[j]=b[j]$, et que $a[i]<b[i]$.
Après avoir appris ces définitions, 小 Y a imaginé le problème suivant.
On vous donne une chaîne $s[1:n]$ de longueur $n$. Il y a $q$ requêtes, chacune donnant deux paramètres $i,r$. Vous devez déterminer le nombre de valeurs de $l$ satisfaisant les conditions suivantes :
- $1\le l\le r$.
- $s[i:i+l-1]$ est strictement inférieure à $R(s[i+l:i+2l-1])$ dans l’ordre lexicographique.
小 Y vous demande de l’aider à résoudre ce problème.
Entrée
Les données sont lues dans le fichier string.in.
Ce problème comporte plusieurs jeux de données.
La première ligne contient deux entiers $c,t$, représentant respectivement le numéro du test et le nombre de jeux de données. $c=0$ indique qu’il s’agit d’un exemple.
Les jeux de données sont ensuite fournis successivement. Pour chaque jeu de données :
La première ligne contient deux entiers strictement positifs $n,q$, la longueur de la chaîne et le nombre de requêtes.
La deuxième ligne contient une chaîne $s$ de longueur $n$, composée uniquement de lettres minuscules.
Chacune des $q$ lignes suivantes contient deux entiers strictement positifs $i,r$, représentant une requête. On garantit que $i+2r-1\le n$.
Sortie
Écrivez la sortie dans le fichier string.out.
Pour chaque requête de chaque jeu de données, affichez une ligne contenant un entier : le nombre de valeurs de $l$ satisfaisant les conditions.
Exemples
Entrée 1
0 2 9 3 abacababa 1 4 2 4 3 3 9 3 abaabaaba 1 4 2 4 3 3
Sortie 1
4 0 3 2 0 2
Remarque
Pour la première requête du premier jeu de données :
- Si $l=1$, $s[i:i+l-1]=\mathtt{a}$ et $R(s[i+l:i+l+l-1])=\mathtt{b}$.
- Si $l=2$, $s[i:i+l-1]=\mathtt{ab}$ et $R(s[i+l:i+l+l-1])=\mathtt{ca}$.
- Si $l=3$, $s[i:i+l-1]=\mathtt{aba}$ et $R(s[i+l:i+l+l-1])=\mathtt{bac}$.
- Si $l=4$, $s[i:i+l-1]=\mathtt{abac}$ et $R(s[i+l:i+l+l-1])=\mathtt{baba}$.
Dans ces quatre cas, $s[i:i+l-1]$ est strictement inférieure à $R(s[i+l:i+2l-1])$ dans l’ordre lexicographique ; la réponse est donc $4$.
Exemples 2
Voir string/string2.in et string/string2.ans dans le répertoire du candidat.
Cet exemple satisfait les contraintes du test $5$.
Exemples 3
Voir string/string3.in et string/string3.ans dans le répertoire du candidat.
Exemples 4
Voir string/string4.in et string/string4.ans dans le répertoire du candidat.
Cet exemple satisfait les contraintes des tests $24\sim25$.
Contraintes
Pour tous les jeux de données, on garantit : $1\le t\le5$, $1\le n\le10^5$, $1\le q\le10^5$, $1\le i+2r-1\le n$ ; la chaîne $s$ contient uniquement des lettres minuscules.
| Numéro du test | $n$ | $q$ | Propriété particulière |
|---|---|---|---|
| $1$ | $\le 5$ | $\le 5$ | A |
| $2$ | $\le 10$ | $\le 10$ | |
| $3$ | $\le 20$ | $\le 20$ | |
| $4$ | $\le 50$ | $\le 50$ | |
| $5$ | $\le 10^2$ | $\le 10^2$ | |
| $6$ | $\le 10^3$ | $\le 10^3$ | Aucune |
| $7$ | $\le 2\,000$ | $\le 2\,000$ | |
| $8$ | $\le 3\,000$ | $\le 3\,000$ | |
| $9$ | $\le 4\,000$ | $\le 4\,000$ | |
| $10$ | $\le 23\,333$ | $\le 23\,333$ | A |
| $11$ | $\le 5\times10^4$ | $\le 5\times10^4$ | |
| $12$ | $\le 75\,000$ | $\le 75\,000$ | |
| $13$ | $\le 9\times10^4$ | $\le 9\times10^4$ | |
| $14$ | $\le 10^5$ | $\le 10^5$ | |
| $15$ | $\le 23\,333$ | $\le 23\,333$ | B |
| $16$ | $\le 75\,000$ | $\le 75\,000$ | |
| $17$ | $\le 9\times10^4$ | $\le 9\times10^4$ | |
| $18$ | $\le 10^5$ | $\le 10^5$ | |
| $19$ | $\le 23\,333$ | $\le 23\,333$ | Aucune |
| $20$ | $\le 5\times10^4$ | $\le 5\times10^4$ | |
| $21$ | $\le 75\,000$ | $\le 75\,000$ | |
| $22$ | $\le 9\times10^4$ | $\le 9\times10^4$ | |
| $23$ | $\le 95\,000$ | $\le 95\,000$ | |
| $24$ | $\le 10^5$ | $\le 10^5$ | |
| $25$ |
- Propriété particulière A : la chaîne contient uniquement les caractères
aetb, et chaque caractère est choisi indépendamment, avec la même probabilité pouraet pourb. - Propriété particulière B : deux caractères adjacents de la chaîne sont toujours différents.