Cleopatra ama le stringhe. Quando le viene data una stringa $s$ di lunghezza $n$ (composta dai caratteri $s[1], \dots, s[n]$), inizia immediatamente a ordinarla. Durante il processo di ordinamento, esegue una sequenza di scambi della forma $s[i] \leftrightarrow s[i + 1]$, dove $i \in \{1, 2, \dots, n - 1\}$. Alla fine, restituisce la stringa ordinata e pretende un numero di monete d'oro pari alla somma di $i$ per tutti gli scambi effettuati (se uno scambio è stato effettuato più volte con lo stesso $i$, allora quell'$i$ verrà contato nella somma tante volte quante è stato scambiato). Cleopatra non è sprecona: tra tutti i modi per ordinare la stringa, sceglie quello in cui il numero di monete che riceve per l'ordinamento è minimo.
Anche Caterina de' Medici ama le stringhe. Ha una stringa di lunghezza $n$ e vuole giocarci. In particolare, è interessata alle seguenti operazioni:
- "
1 i c" — sostituire $s[i]$ con $c$; - "
2 i j" — prendere una copia della sottostringa di $s$ dall'$i$-esimo al $j$-esimo carattere inclusi ($i \le j$) e ordinarla, mentre i caratteri della stringa $s$ rimangono invariati. - "
3 i j" — estrarre la sottostringa di $s$ dall'$i$-esimo al $j$-esimo carattere inclusi ($i \le j$), ordinarla e reinserirla nella stringa $s$ nella stessa posizione.
Caterina de' Medici può gestire da sola le query del primo tipo, ma le query del secondo e del terzo tipo sono troppo complesse e per quelle si rivolgerà a Cleopatra. Nel valutare il costo di questa procedura, Cleopatra sommerà non gli indici della stringa $s$ (da $i$ a $j$), bensì gli indici relativi all'inizio della sottostringa (da $1$ a $j - i + 1$).
Anche Caterina de' Medici non è sprecona e controlla attentamente il suo budget. Pertanto, per ciascuna delle sue richieste a Cleopatra, calcola quante monete d'oro dovrà spendere Caterina de' Medici.
Input
La prima riga dell'input contiene un intero $t$ — il numero di casi di test ($1 \le t \le 3 \cdot 10^5$). Per ciascun caso di test:
La prima riga contiene due interi, $n$ e $q$ — la lunghezza della stringa e il numero di query ($1 \le n, q \le 3 \cdot 10^5$). La riga successiva contiene una stringa di $n$ lettere maiuscole dell'alfabeto inglese. Le seguenti $q$ righe descrivono le query. Ogni descrizione di query appartiene a uno dei tre tipi:
- "
1 i c" — sostituire $s[i]$ con $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — trovare il costo per ordinare la sottostringa $s[i..j]$, mentre la stringa $s$ rimane invariata ($1 \le i, j \le n$); - "
3 i j" — trovare il costo per ordinare la sottostringa $s[i..j]$, mentre la sottostringa $s[i..j]$ nella stringa $s$ viene sostituita con quella ordinata ($1 \le i, j \le n$).
In ciascun caso di test ci sarà almeno una query del secondo o del terzo tipo.
La somma di $n$ su tutti i casi di test è al massimo $3 \cdot 10^5$. La somma di $q$ su tutti i casi di test è al massimo $3 \cdot 10^5$.
Output
Per ciascun caso di test, stampa su righe separate le risposte a tutte le query del secondo e del terzo tipo, ossia il numero di monete che Cleopatra riceverà per ciascuno degli ordinamenti.
Esempi
Input 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
Output 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Input 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
Output 2
4 4 0 0 0 9 9 0 0 3 1 1
Note
Consideriamo il primo esempio. In esso, la stringa iniziale è "DBCAA". Esaminiamo tutte le 20 query in ordine:
- Query "
2 1 5". Stringa corrente: "DBCAA". Sottostringa $t[1..5]$ = "DBCAA", risposta: 18. La stringa non cambia. - Query "
2 2 4". Stringa: "DBCAA". Sottostringa $t[2..4]$ = "BCA", risposta: 3. La stringa non cambia. - Query "
1 3 Z". Aggiornamento: $t[3] \leftarrow$ "Z". Era "DBCAA", ora è "DBZAA". - Query "
2 1 3". Stringa: "DBZAA". Sottostringa $t[1..3]$ = "DBZ", risposta: 1. La stringa non cambia. - Query "
3 1 5". Stringa: "DBZAA". Sottostringa $t[1..5]$ = "DBZAA", risposta: 16. Dopo la modifica, ordinando la sottostringa: "DBZAA" $\rightarrow$ "AABDZ". La stringa è diventata "AABDZ". - Query "
2 1 5". Stringa: "AABDZ". Sottostringa "AABDZ", risposta: 0. La stringa non cambia. - Query "
1 5 A". Era "AABDZ", ora è "AABDA". - Query "
3 2 4". Stringa: "AABDA". Sottostringa $t[2..4]$ = "ABD", risposta: 0. Dopo l'ordinamento "ABD" non cambia, la stringa rimane "AABDA". - Query "
2 1 5". Stringa: "AABDA". Sottostringa "AABDA", risposta: 7. La stringa non cambia. - Query "
1 1 C". Era "AABDA", ora è "CABDA". - Query "
2 1 2". Stringa: "CABDA". Sottostringa $t[1..2]$ = "CA", risposta: 1. La stringa non cambia. - Query "
3 4 5". Stringa: "CABDA". Sottostringa $t[4..5]$ = "DA", risposta: 1. Dopo la modifica: "DA" $\rightarrow$ "AD". La stringa è diventata "CABAD". - Query "
2 3 5". Stringa: "CABAD". Sottostringa $t[3..5]$ = "BAD", risposta: 1. La stringa non cambia. - Query "
1 2 B". Era "CABAD", ora è "CBBAD". - Query "
2 1 5". Stringa: "CBBAD". Sottostringa "CBBAD", risposta: 9. La stringa non cambia. - Query "
3 1 1". Stringa: "CBBAD". Sottostringa $t[1..1]$ = "C", risposta: 0. Ordinare una lunghezza pari a 1 non cambia nulla, la stringa rimane "CBBAD". - Query "
2 1 1". Stringa: "CBBAD". Sottostringa $t[1..1]$ = "C", risposta: 0. La stringa non cambia. - Query "
1 4 D". Era "CBBAD", ora è "CBBDD". - Query "
2 1 5". Stringa: "CBBDD". Sottostringa $t[1..5]$ = "CBBDD", risposta: 3. La stringa non cambia. - Query "
3 1 5". Stringa: "CBBDD". Sottostringa $t[1..5]$ = "CBBDD", risposta: 3. Dopo la modifica: "CBBDD" $\rightarrow$ "BBCDD". La stringa finale è "BBCDD".