Y es un estudiante universitario que últimamente investiga problemas sobre cadenas.
Ha aprendido las siguientes definiciones sobre cadenas:
- Para una cadena $s[1:n]$ de longitud $n$, su subcadena $s[l:r]$ ($1\leq l\leq r\leq n$) es la nueva cadena obtenida al concatenar $s[l],s[l+1],\ldots,s[r]$ en ese orden.
- Para una cadena $s[1:n]$ de longitud $n$, su inversa $R(s)$ se obtiene concatenando $s[n],s[n-1],\ldots,s[1]$ en ese orden; es decir, concatenando la cadena en orden inverso.
- Para dos cadenas $a[1:n],b[1:n]$ de longitud $n$, se define que $a$ es lexicográficamente menor que $b$ si y solo si existe $1\leq i\leq n$ tal que, para todo $1\leq j<i$, se cumple $a[j]=b[j]$, y además $a[i]<b[i]$.
Tras aprender estas definiciones, Y se ha planteado el siguiente problema:
Se da una cadena $s[1:n]$ de longitud $n$. Hay $q$ consultas, cada una con dos parámetros $i,r$. Debes calcular cuántos valores de $l$ satisfacen las condiciones siguientes:
- $1\leq l\leq r$.
- $s[i:i+l-1]$ es lexicográficamente menor que $R(s[i+l:i+2l-1])$.
Y quiere pedirte ayuda para resolverlo.
Entrada
Los datos se leen del archivo string.in.
Este problema tiene varios casos de prueba.
La primera línea contiene dos enteros $c,t$: el número del punto de prueba y el número de casos de prueba, respectivamente. $c=0$ indica que se trata de un ejemplo.
A continuación se dan los casos de prueba, uno tras otro. Para cada caso:
La primera línea contiene dos enteros positivos $n,q$: la longitud de la cadena y el número de consultas.
La segunda línea contiene una cadena $s$ de longitud $n$ formada únicamente por letras minúsculas.
Cada una de las siguientes $q$ líneas contiene dos enteros positivos $i,r$ que describen una consulta. Se garantiza que $i+2r-1\leq n$.
Salida
La salida se escribe en el archivo string.out.
Para cada consulta de cada caso de prueba, imprime una línea con un entero: el número de valores de $l$ que cumplen las condiciones.
Ejemplos
Entrada 1
0 2 9 3 abacababa 1 4 2 4 3 3 9 3 abaabaaba 1 4 2 4 3 3
Salida 1
4 0 3 2 0 2
Nota
Para la primera consulta del primer caso:
- Si $l=1$, $s[i:i+l-1]=\mathrm{a}$ y $R(s[i+l:i+l+l-1])=\mathrm{b}$.
- Si $l=2$, $s[i:i+l-1]=\mathrm{ab}$ y $R(s[i+l:i+l+l-1])=\mathrm{ca}$.
- Si $l=3$, $s[i:i+l-1]=\mathrm{aba}$ y $R(s[i+l:i+l+l-1])=\mathrm{bac}$.
- Si $l=4$, $s[i:i+l-1]=\mathrm{abac}$ y $R(s[i+l:i+l+l-1])=\mathrm{baba}$.
En los cuatro casos, $s[i:i+l-1]$ es lexicográficamente menor que $R(s[i+l:i+2l-1])$, por lo que la respuesta es $4$.
Ejemplo 2
Consulta string/string2.in y string/string2.ans en el directorio del concursante.
Las restricciones de este ejemplo corresponden al punto de prueba $5$.
Ejemplo 3
Consulta string/string3.in y string/string3.ans en el directorio del concursante.
Ejemplo 4
Consulta string/string4.in y string/string4.ans en el directorio del concursante.
Las restricciones de este ejemplo corresponden a los puntos de prueba $24\sim25$.
Restricciones
Para todos los datos se garantiza que $1\leq t\leq5$, $1\leq n\leq10^5$, $1\leq q\leq10^5$, $1\leq i+2r-1\leq n$, y que $s$ solo contiene letras minúsculas.
| Punto de prueba | $n$ | $q$ | Propiedad especial |
|---|---|---|---|
| $1$ | $\leq5$ | $\leq5$ | A |
| $2$ | $\leq10$ | $\leq10$ | |
| $3$ | $\leq20$ | $\leq20$ | |
| $4$ | $\leq50$ | $\leq50$ | |
| $5$ | $\leq10^2$ | $\leq10^2$ | |
| $6$ | $\leq10^3$ | $\leq10^3$ | Ninguna |
| $7$ | $\leq2\,000$ | $\leq2\,000$ | |
| $8$ | $\leq3\,000$ | $\leq3\,000$ | |
| $9$ | $\leq4\,000$ | $\leq4\,000$ | |
| $10$ | $\leq23\,333$ | $\leq23\,333$ | A |
| $11$ | $\leq5\times10^4$ | $\leq5\times10^4$ | |
| $12$ | $\leq75\,000$ | $\leq75\,000$ | |
| $13$ | $\leq9\times10^4$ | $\leq9\times10^4$ | |
| $14$ | $\leq10^5$ | $\leq10^5$ | |
| $15$ | $\leq23\,333$ | $\leq23\,333$ | B |
| $16$ | $\leq75\,000$ | $\leq75\,000$ | |
| $17$ | $\leq9\times10^4$ | $\leq9\times10^4$ | |
| $18$ | $\leq10^5$ | $\leq10^5$ | |
| $19$ | $\leq23\,333$ | $\leq23\,333$ | Ninguna |
| $20$ | $\leq5\times10^4$ | $\leq5\times10^4$ | |
| $21$ | $\leq75\,000$ | $\leq75\,000$ | |
| $22$ | $\leq9\times10^4$ | $\leq9\times10^4$ | |
| $23$ | $\leq95\,000$ | $\leq95\,000$ | |
| $24$ | $\leq10^5$ | $\leq10^5$ | |
| $25$ |
- Propiedad especial A: se garantiza que la cadena solo contiene los caracteres
ayb, y que cada carácter se elige entreaybde forma independiente y con igual probabilidad. - Propiedad especial B: se garantiza que los caracteres adyacentes de la cadena son distintos.