Kleopatra uwielbia napisy. Gdy dostaje napis $s$ o długości $n$ (składający się ze znaków $s[1], \dots, s[n]$), natychmiast zaczyna go sortować. Podczas procesu sortowania wykonuje ciąg zamian postaci $s[i] \leftrightarrow s[i + 1]$, gdzie $i \in \{1, 2, \dots, n - 1\}$. Na koniec zwraca posortowany napis i żąda liczby złotych monet równej sumie indeksów $i$ ze wszystkich wykonanych zamian (jeśli zamiana została wykonana wielokrotnie dla tego samego $i$, to owo $i$ zostanie policzone w sumie tyle razy, ile razy wykonano zamianę). Kleopatra nie jest rozrzutna: spośród wszystkich sposobów posortowania napisu wybiera ten, przy którym liczba monet otrzymanych za sortowanie jest minimalna.
Katarzyna Medycejska również uwielbia napisy. Ma napis o długości $n$ i chce się nim pobawić. Konkretnie interesują ją następujące operacje:
- "
1 i c" — zamień $s[i]$ na $c$; - "
2 i j" — weź kopię podsłowa napisu $s$ od $i$-tego do $j$-tego znaku włącznie ($i \le j$) i posortuj ją, podczas gdy znaki napisu $s$ pozostają bez zmian. - "
3 i j" — wytnij podsłowo napisu $s$ od $i$-tego do $j$-tego znaku włącznie ($i \le j$), posortuj je i wstaw z powrotem do napisu $s$ na to samo miejsce.
Katarzyna Medycejska potrafi sama obsłużyć zapytania pierwszego typu, ale zapytania drugiego i trzeciego typu są zbyt skomplikowane, więc uda się z nimi do Kleopatry. Przy wycenie kosztu tej procedury Kleopatra będzie sumować nie indeksy z napisu $s$ (od $i$ do $j$), lecz indeksy liczone względem początku podsłowa (od $1$ do $j - i + 1$).
Katarzyna Medycejska również nie jest rozrzutna i uważnie pilnuje swojego budżetu. Dlatego dla każdego jej zlecenia skierowanego do Kleopatry oblicz, ile złotych monet Katarzyna Medycejska będzie musiała wydać.
Wejście
Pierwszy wiersz wejścia zawiera liczbę całkowitą $t$ — liczbę przypadków testowych ($1 \le t \le 3 \cdot 10^5$). Dla każdego przypadku testowego:
Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $q$ — długość napisu oraz liczbę zapytań ($1 \le n, q \le 3 \cdot 10^5$). Następny wiersz zawiera napis złożony z $n$ wielkich liter alfabetu angielskiego. Kolejne $q$ wierszy opisuje zapytania. Każdy opis zapytania należy do jednego z trzech typów:
- "
1 i c" — zamień $s[i]$ na $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — wyznacz koszt posortowania podsłowa $s[i..j]$, podczas gdy napis $s$ pozostaje bez zmian ($1 \le i, j \le n$); - "
3 i j" — wyznacz koszt posortowania podsłowa $s[i..j]$, przy czym podsłowo $s[i..j]$ w napisie $s$ zostaje zastąpione posortowanym ($1 \le i, j \le n$).
W każdym przypadku testowym wystąpi co najmniej jedno zapytanie drugiego lub trzeciego typu.
Suma $n$ po wszystkich przypadkach testowych wynosi co najwyżej $3 \cdot 10^5$. Suma $q$ po wszystkich przypadkach testowych wynosi co najwyżej $3 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz w osobnych wierszach odpowiedzi na wszystkie zapytania drugiego i trzeciego typu, czyli liczbę monet, które Kleopatra otrzyma za każde z sortowań.
Przykłady
Wejście 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
Wyjście 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Wejście 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
Wyjście 2
4 4 0 0 0 9 9 0 0 3 1 1
Uwaga
Rozważmy pierwszy przykład. Początkowy napis w nim to "DBCAA". Przejdźmy po kolei przez wszystkie 20 zapytań:
- Zapytanie "
2 1 5". Bieżący napis: "DBCAA". Podsłowo $t[1..5]$ = "DBCAA", odpowiedź: 18. Napis się nie zmienia. - Zapytanie "
2 2 4". Napis: "DBCAA". Podsłowo $t[2..4]$ = "BCA", odpowiedź: 3. Napis się nie zmienia. - Zapytanie "
1 3 Z". Aktualizacja: $t[3] \leftarrow$ "Z". Było "DBCAA", teraz "DBZAA". - Zapytanie "
2 1 3". Napis: "DBZAA". Podsłowo $t[1..3]$ = "DBZ", odpowiedź: 1. Napis się nie zmienia. - Zapytanie "
3 1 5". Napis: "DBZAA". Podsłowo $t[1..5]$ = "DBZAA", odpowiedź: 16. Po zmianie, sortowanie podsłowa: "DBZAA" $\rightarrow$ "AABDZ". Napis stał się równy "AABDZ". - Zapytanie "
2 1 5". Napis: "AABDZ". Podsłowo "AABDZ", odpowiedź: 0. Napis się nie zmienia. - Zapytanie "
1 5 A". Było "AABDZ", teraz "AABDA". - Zapytanie "
3 2 4". Napis: "AABDA". Podsłowo $t[2..4]$ = "ABD", odpowiedź: 0. Po posortowaniu "ABD" się nie zmienia, napis pozostaje równy "AABDA". - Zapytanie "
2 1 5". Napis: "AABDA". Podsłowo "AABDA", odpowiedź: 7. Napis się nie zmienia. - Zapytanie "
1 1 C". Było "AABDA", teraz "CABDA". - Zapytanie "
2 1 2". Napis: "CABDA". Podsłowo $t[1..2]$ = "CA", odpowiedź: 1. Napis się nie zmienia. - Zapytanie "
3 4 5". Napis: "CABDA". Podsłowo $t[4..5]$ = "DA", odpowiedź: 1. Po zmianie: "DA" $\rightarrow$ "AD". Napis stał się równy "CABAD". - Zapytanie "
2 3 5". Napis: "CABAD". Podsłowo $t[3..5]$ = "BAD", odpowiedź: 1. Napis się nie zmienia. - Zapytanie "
1 2 B". Było "CABAD", teraz "CBBAD". - Zapytanie "
2 1 5". Napis: "CBBAD". Podsłowo "CBBAD", odpowiedź: 9. Napis się nie zmienia. - Zapytanie "
3 1 1". Napis: "CBBAD". Podsłowo $t[1..1]$ = "C", odpowiedź: 0. Sortowanie długości 1 nic nie zmienia, napis pozostaje równy "CBBAD". - Zapytanie "
2 1 1". Napis: "CBBAD". Podsłowo $t[1..1]$ = "C", odpowiedź: 0. Napis się nie zmienia. - Zapytanie "
1 4 D". Było "CBBAD", teraz "CBBDD". - Zapytanie "
2 1 5". Napis: "CBBDD". Podsłowo $t[1..5]$ = "CBBDD", odpowiedź: 3. Napis się nie zmienia. - Zapytanie "
3 1 5". Napis: "CBBDD". Podsłowo $t[1..5]$ = "CBBDD", odpowiedź: 3. Po zmianie: "CBBDD" $\rightarrow$ "BBCDD". Ostateczny napis to "BBCDD".