Cleopatra menyukai string. Ketika ia diberi sebuah string $s$ dengan panjang $n$ (terdiri dari karakter $s[1], \dots, s[n]$), ia segera mulai mengurutkannya. Selama proses pengurutan, ia melakukan serangkaian pertukaran berbentuk $s[i] \leftrightarrow s[i + 1]$, dengan $i \in \{1, 2, \dots, n - 1\}$. Pada akhirnya, ia mengembalikan string yang telah terurut dan meminta sejumlah koin emas yang sama dengan jumlah seluruh $i$ dari semua pertukaran yang dilakukan (jika suatu pertukaran dilakukan beberapa kali dengan $i$ yang sama, maka nilai $i$ tersebut akan dihitung dalam penjumlahan sebanyak jumlah pertukarannya). Cleopatra tidak boros: di antara semua cara untuk mengurutkan string tersebut, ia memilih cara yang membuat jumlah koin yang ia terima paling sedikit.
Catherine de' Medici juga menyukai string. Ia memiliki sebuah string dengan panjang $n$, dan ia ingin bermain dengannya. Secara khusus, ia tertarik pada operasi-operasi berikut:
- "
1 i c" — mengganti $s[i]$ dengan $c$; - "
2 i j" — mengambil salinan substring $s$ dari karakter ke-$i$ hingga ke-$j$ inklusif ($i \le j$) lalu mengurutkannya, sementara karakter-karakter pada string $s$ tetap tidak berubah. - "
3 i j" — mengambil substring $s$ dari karakter ke-$i$ hingga ke-$j$ inklusif ($i \le j$), mengurutkannya, lalu memasukkannya kembali ke dalam string $s$ pada posisi yang sama.
Catherine de' Medici dapat menangani kueri jenis pertama sendiri, tetapi kueri jenis kedua dan ketiga terlalu rumit, sehingga ia akan meminta bantuan Cleopatra. Saat menilai biaya prosedur ini, Cleopatra tidak akan menjumlahkan indeks dari string $s$ (dari $i$ hingga $j$), melainkan indeks relatif terhadap awal substring (dari $1$ hingga $j - i + 1$).
Catherine de' Medici juga tidak boros dan memantau anggarannya dengan cermat. Oleh karena itu, untuk setiap permintaannya kepada Cleopatra, hitunglah berapa banyak koin emas yang harus dikeluarkan oleh Catherine de' Medici.
Masukan
Baris pertama masukan berisi sebuah bilangan bulat $t$ — banyaknya kasus uji ($1 \le t \le 3 \cdot 10^5$). Untuk setiap kasus uji:
Baris pertama berisi dua bilangan bulat, $n$ dan $q$ — panjang string dan banyaknya kueri ($1 \le n, q \le 3 \cdot 10^5$). Baris berikutnya berisi sebuah string yang terdiri dari $n$ huruf kapital bahasa Inggris. $q$ baris berikutnya menjelaskan kueri. Setiap deskripsi kueri memiliki salah satu dari tiga jenis berikut:
- "
1 i c" — mengganti $s[i]$ dengan $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — mencari biaya pengurutan substring $s[i..j]$, sementara string $s$ tetap tidak berubah ($1 \le i, j \le n$); - "
3 i j" — mencari biaya pengurutan substring $s[i..j]$, sementara substring $s[i..j]$ di dalam string $s$ digantikan dengan yang sudah terurut ($1 \le i, j \le n$).
Pada setiap kasus uji, akan terdapat setidaknya satu kueri dari jenis kedua atau ketiga.
Jumlah $n$ di semua kasus uji paling banyak adalah $3 \cdot 10^5$. Jumlah $q$ di semua kasus uji paling banyak adalah $3 \cdot 10^5$.
Keluaran
Untuk setiap kasus uji, keluarkan pada baris terpisah jawaban untuk semua kueri jenis kedua dan ketiga, yaitu banyaknya koin yang akan diterima Cleopatra untuk setiap pengurutan.
Contoh
Masukan 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
Keluaran 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Masukan 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
Keluaran 2
4 4 0 0 0 9 9 0 0 3 1 1
Catatan
Perhatikan contoh pertama. Di dalamnya, string awal adalah "DBCAA". Mari kita telusuri ke-20 kueri secara berurutan:
- Kueri "
2 1 5". String saat ini: "DBCAA". Substring $t[1..5]$ = "DBCAA", jawaban: 18. String tidak berubah. - Kueri "
2 2 4". String: "DBCAA". Substring $t[2..4]$ = "BCA", jawaban: 3. String tidak berubah. - Kueri "
1 3 Z". Pembaruan: $t[3] \leftarrow$ "Z". Semula "DBCAA", sekarang "DBZAA". - Kueri "
2 1 3". String: "DBZAA". Substring $t[1..3]$ = "DBZ", jawaban: 1. String tidak berubah. - Kueri "
3 1 5". String: "DBZAA". Substring $t[1..5]$ = "DBZAA", jawaban: 16. Setelah mutasi, mengurutkan substring: "DBZAA" $\rightarrow$ "AABDZ". String menjadi "AABDZ". - Kueri "
2 1 5". String: "AABDZ". Substring "AABDZ", jawaban: 0. String tidak berubah. - Kueri "
1 5 A". Semula "AABDZ", sekarang "AABDA". - Kueri "
3 2 4". String: "AABDA". Substring $t[2..4]$ = "ABD", jawaban: 0. Setelah pengurutan "ABD" tidak berubah, string tetap "AABDA". - Kueri "
2 1 5". String: "AABDA". Substring "AABDA", jawaban: 7. String tidak berubah. - Kueri "
1 1 C". Semula "AABDA", sekarang "CABDA". - Kueri "
2 1 2". String: "CABDA". Substring $t[1..2]$ = "CA", jawaban: 1. String tidak berubah. - Kueri "
3 4 5". String: "CABDA". Substring $t[4..5]$ = "DA", jawaban: 1. Setelah mutasi: "DA" $\rightarrow$ "AD". String menjadi "CABAD". - Kueri "
2 3 5". String: "CABAD". Substring $t[3..5]$ = "BAD", jawaban: 1. String tidak berubah. - Kueri "
1 2 B". Semula "CABAD", sekarang "CBBAD". - Kueri "
2 1 5". String: "CBBAD". Substring "CBBAD", jawaban: 9. String tidak berubah. - Kueri "
3 1 1". String: "CBBAD". Substring $t[1..1]$ = "C", jawaban: 0. Mengurutkan panjang 1 tidak mengubah apa pun, string tetap "CBBAD". - Kueri "
2 1 1". String: "CBBAD". Substring $t[1..1]$ = "C", jawaban: 0. String tidak berubah. - Kueri "
1 4 D". Semula "CBBAD", sekarang "CBBDD". - Kueri "
2 1 5". String: "CBBDD". Substring $t[1..5]$ = "CBBDD", jawaban: 3. String tidak berubah. - Kueri "
3 1 5". String: "CBBDD". Substring $t[1..5]$ = "CBBDD", jawaban: 3. Setelah mutasi: "CBBDD" $\rightarrow$ "BBCDD". String akhir adalah "BBCDD".