A Cleopatra le encantan las cadenas. Cuando le dan una cadena $s$ de longitud $n$ (compuesta por los caracteres $s[1], \dots, s[n]$), inmediatamente comienza a ordenarla. Durante el proceso de ordenamiento, realiza una secuencia de intercambios de la forma $s[i] \leftrightarrow s[i + 1]$, donde $i \in \{1, 2, \dots, n - 1\}$. Al final, devuelve la cadena ordenada y exige una cantidad de monedas de oro igual a la suma de $i$ para todos los intercambios realizados (si un intercambio se realizó múltiples veces con el mismo $i$, entonces ese $i$ se contará en la suma tantas veces como se haya intercambiado). Cleopatra no es derrochadora: entre todas las formas de ordenar la cadena, elige aquella en la que el número de monedas que recibe por ordenar es mínimo.
A Catalina de Médici también le encantan las cadenas. Tiene una cadena de longitud $n$ y quiere jugar con ella. Específicamente, está interesada en las siguientes operaciones:
- "
1 i c" — reemplazar $s[i]$ por $c$; - "
2 i j" — tomar una copia de la subcadena de $s$ desde el $i$-ésimo hasta el $j$-ésimo carácter inclusive ($i \le j$) y ordenarla, mientras que los caracteres de la cadena $s$ permanecen sin cambios. - "
3 i j" — extraer la subcadena de $s$ desde el $i$-ésimo hasta el $j$-ésimo carácter inclusive ($i \le j$), ordenarla e insertarla de nuevo en la cadena $s$ en la misma posición.
Catalina de Médici puede encargarse ella misma de las consultas del primer tipo, pero las consultas del segundo y tercer tipo son demasiado complejas y acudirá a Cleopatra para realizarlas. Al evaluar el costo de este procedimiento, Cleopatra sumará no los índices de la cadena $s$ (de $i$ a $j$), sino los índices relativos al comienzo de la subcadena (de $1$ a $j - i + 1$).
Catalina de Médici tampoco es derrochadora y supervisa cuidadosamente su presupuesto. Por lo tanto, para cada una de sus solicitudes a Cleopatra, calcula cuántas monedas de oro tendrá que gastar Catalina de Médici.
Entrada
La primera línea de la entrada contiene un entero $t$ — el número de casos de prueba ($1 \le t \le 3 \cdot 10^5$). Para cada caso de prueba:
La primera línea contiene dos enteros, $n$ y $q$ — la longitud de la cadena y el número de consultas ($1 \le n, q \le 3 \cdot 10^5$). La siguiente línea contiene una cadena de $n$ letras inglesas mayúsculas. Las siguientes $q$ líneas describen las consultas. Cada descripción de consulta tiene uno de los tres tipos:
- "
1 i c" — reemplazar $s[i]$ por $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — hallar el costo de ordenar la subcadena $s[i..j]$, mientras la cadena $s$ permanece sin cambios ($1 \le i, j \le n$); - "
3 i j" — hallar el costo de ordenar la subcadena $s[i..j]$, mientras la subcadena $s[i..j]$ en la cadena $s$ se reemplaza por la subcadena ordenada ($1 \le i, j \le n$).
En cada caso de prueba habrá al menos una consulta del segundo o tercer tipo.
La suma de $n$ en todos los casos de prueba es a lo sumo $3 \cdot 10^5$. La suma de $q$ en todos los casos de prueba es a lo sumo $3 \cdot 10^5$.
Salida
Para cada caso de prueba, imprime en una línea separada las respuestas a todas las consultas del segundo y tercer tipo, es decir, el número de monedas que recibirá Cleopatra por cada uno de los ordenamientos.
Ejemplos
Entrada 1
1 5 20 DBCAA 2 1 5 2 2 4 1 3 Z 2 1 3 3 1 5 2 1 5 1 5 A 3 2 4 2 1 5 1 1 C 2 1 2 3 4 5 2 3 5 1 2 B 2 1 5 3 1 1 2 1 1 1 4 D 2 1 5 3 1 5
Salida 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Entrada 2
3 3 5 CBA 2 1 3 3 1 3 2 1 3 1 2 C 2 1 2 5 5 ABCDE 2 2 5 1 5 A 2 1 5 3 1 5 2 1 5 6 5 YYYYYY 2 1 6 1 3 A 2 1 6 3 2 5 2 1 6
Salida 2
4 4 0 0 0 9 9 0 0 3 1 1
Nota
Consideremos el primer ejemplo. En él, la cadena inicial es "DBCAA". Repasemos las 20 consultas en orden:
- Consulta "
2 1 5". Cadena actual: "DBCAA". Subcadena $t[1..5]$ = "DBCAA", respuesta: 18. La cadena no cambia. - Consulta "
2 2 4". Cadena: "DBCAA". Subcadena $t[2..4]$ = "BCA", respuesta: 3. La cadena no cambia. - Consulta "
1 3 Z". Actualización: $t[3] \leftarrow$ "Z". Era "DBCAA", ahora es "DBZAA". - Consulta "
2 1 3". Cadena: "DBZAA". Subcadena $t[1..3]$ = "DBZ", respuesta: 1. La cadena no cambia. - Consulta "
3 1 5". Cadena: "DBZAA". Subcadena $t[1..5]$ = "DBZAA", respuesta: 16. Tras la mutación, ordenando la subcadena: "DBZAA" $\rightarrow$ "AABDZ". La cadena pasó a ser "AABDZ". - Consulta "
2 1 5". Cadena: "AABDZ". Subcadena "AABDZ", respuesta: 0. La cadena no cambia. - Consulta "
1 5 A". Era "AABDZ", ahora es "AABDA". - Consulta "
3 2 4". Cadena: "AABDA". Subcadena $t[2..4]$ = "ABD", respuesta: 0. Tras ordenar, "ABD" no cambia, la cadena sigue siendo "AABDA". - Consulta "
2 1 5". Cadena: "AABDA". Subcadena "AABDA", respuesta: 7. La cadena no cambia. - Consulta "
1 1 C". Era "AABDA", ahora es "CABDA". - Consulta "
2 1 2". Cadena: "CABDA". Subcadena $t[1..2]$ = "CA", respuesta: 1. La cadena no cambia. - Consulta "
3 4 5". Cadena: "CABDA". Subcadena $t[4..5]$ = "DA", respuesta: 1. Tras la mutación: "DA" $\rightarrow$ "AD". La cadena pasó a ser "CABAD". - Consulta "
2 3 5". Cadena: "CABAD". Subcadena $t[3..5]$ = "BAD", respuesta: 1. La cadena no cambia. - Consulta "
1 2 B". Era "CABAD", ahora es "CBBAD". - Consulta "
2 1 5". Cadena: "CBBAD". Subcadena "CBBAD", respuesta: 9. La cadena no cambia. - Consulta "
3 1 1". Cadena: "CBBAD". Subcadena $t[1..1]$ = "C", respuesta: 0. Ordenar una longitud de 1 no cambia nada, la cadena sigue siendo "CBBAD". - Consulta "
2 1 1". Cadena: "CBBAD". Subcadena $t[1..1]$ = "C", respuesta: 0. La cadena no cambia. - Consulta "
1 4 D". Era "CBBAD", ahora es "CBBDD". - Consulta "
2 1 5". Cadena: "CBBDD". Subcadena $t[1..5]$ = "CBBDD", respuesta: 3. La cadena no cambia. - Consulta "
3 1 5". Cadena: "CBBDD". Subcadena $t[1..5]$ = "CBBDD", respuesta: 3. Tras la mutación: "CBBDD" $\rightarrow$ "BBCDD". La cadena final es "BBCDD".