Cleopatra rất yêu thích các xâu ký tự. Khi được đưa một xâu $s$ có độ dài $n$ (bao gồm các ký tự $s[1], \dots, s[n]$), bà lập tức bắt đầu sắp xếp nó. Trong quá trình sắp xếp, bà thực hiện một dãy các phép hoán đổi có dạng $s[i] \leftrightarrow s[i + 1]$, với $i \in \{1, 2, \dots, n - 1\}$. Cuối cùng, bà trả lại xâu đã được sắp xếp và yêu cầu số lượng đồng tiền vàng bằng tổng các chỉ số $i$ của tất cả các phép hoán đổi đã thực hiện (nếu một phép hoán đổi được thực hiện nhiều lần với cùng một chỉ số $i$, thì chỉ số $i$ đó sẽ được tính vào tổng bấy nhiêu lần). Cleopatra không hề lãng phí: trong tất cả các cách để sắp xếp xâu, bà chọn cách mà số đồng tiền vàng bà nhận được cho việc sắp xếp là ít nhất.
Catherine de' Medici cũng yêu thích các xâu ký tự. Bà có một xâu độ dài $n$ và muốn chơi đùa với nó. Cụ thể, bà quan tâm đến các thao tác sau:
- "
1 i c" — thay thế $s[i]$ bằng $c$; - "
2 i j" — lấy một bản sao của xâu con thuộc $s$ từ ký tự thứ $i$ đến ký tự thứ $j$ (tính cả hai đầu, $i \le j$) và sắp xếp nó, trong khi các ký tự của xâu $s$ giữ nguyên không đổi. - "
3 i j" — trích xuất xâu con thuộc $s$ từ ký tự thứ $i$ đến ký tự thứ $j$ (tính cả hai đầu, $i \le j$), sắp xếp nó rồi chèn ngược trở lại vào xâu $s$ tại cùng vị trí đó.
Catherine de' Medici có thể tự mình xử lý các truy vấn loại thứ nhất, nhưng các truy vấn loại thứ hai và thứ ba quá phức tạp nên bà sẽ nhờ đến Cleopatra. Khi tính toán chi phí của quy trình này, Cleopatra sẽ không cộng các chỉ số trong xâu $s$ (từ $i$ đến $j$), mà cộng các chỉ số tương đối tính từ đầu xâu con (từ $1$ đến $j - i + 1$).
Catherine de' Medici cũng không lãng phí và theo dõi ngân sách của mình rất cẩn thận. Do đó, với mỗi yêu cầu của bà gửi tới Cleopatra, hãy tính xem Catherine de' Medici sẽ phải chi bao nhiêu đồng tiền vàng.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$ — số lượng bộ dữ liệu ($1 \le t \le 3 \cdot 10^5$). Đối với mỗi bộ dữ liệu:
Dòng đầu tiên chứa hai số nguyên $n$ và $q$ — độ dài của xâu và số lượng truy vấn ($1 \le n, q \le 3 \cdot 10^5$). Dòng tiếp theo chứa một xâu gồm $n$ chữ cái tiếng Anh in hoa. $q$ dòng tiếp theo mô tả các truy vấn. Mỗi mô tả truy vấn thuộc một trong ba loại:
- "
1 i c" — thay thế $s[i]$ bằng $c$ ($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" — tìm chi phí sắp xếp xâu con $s[i..j]$, trong khi xâu $s$ giữ nguyên không đổi ($1 \le i, j \le n$); - "
3 i j" — tìm chi phí sắp xếp xâu con $s[i..j]$, đồng thời xâu con $s[i..j]$ trong xâu $s$ được thay thế bằng xâu con đã sắp xếp ($1 \le i, j \le n$).
Trong mỗi bộ dữ liệu sẽ có ít nhất một truy vấn thuộc loại thứ hai hoặc thứ ba.
Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $3 \cdot 10^5$. Tổng của $q$ trên tất cả các bộ dữ liệu không vượt quá $3 \cdot 10^5$.
Kết quả
Đối với mỗi bộ dữ liệu, in ra trên các dòng riêng biệt đáp án cho tất cả các truy vấn loại thứ hai và thứ ba, tức là số lượng đồng tiền vàng mà Cleopatra sẽ nhận được cho mỗi lần sắp xếp.
Ví dụ
Dữ liệu vào 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
Kết quả 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
Dữ liệu vào 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
Kết quả 2
4 4 0 0 0 9 9 0 0 3 1 1
Ghi chú
Xét ví dụ đầu tiên. Trong đó, xâu ban đầu là "DBCAA". Hãy lần lượt xem qua cả 20 truy vấn:
- Truy vấn "
2 1 5". Xâu hiện tại: "DBCAA". Xâu con $t[1..5]$ = "DBCAA", đáp án: 18. Xâu không thay đổi. - Truy vấn "
2 2 4". Xâu: "DBCAA". Xâu con $t[2..4]$ = "BCA", đáp án: 3. Xâu không thay đổi. - Truy vấn "
1 3 Z". Cập nhật: $t[3] \leftarrow$ "Z". Trước là "DBCAA", nay là "DBZAA". - Truy vấn "
2 1 3". Xâu: "DBZAA". Xâu con $t[1..3]$ = "DBZ", đáp án: 1. Xâu không thay đổi. - Truy vấn "
3 1 5". Xâu: "DBZAA". Xâu con $t[1..5]$ = "DBZAA", đáp án: 16. Sau khi biến đổi, sắp xếp xâu con: "DBZAA" $\rightarrow$ "AABDZ". Xâu trở thành "AABDZ". - Truy vấn "
2 1 5". Xâu: "AABDZ". Xâu con "AABDZ", đáp án: 0. Xâu không thay đổi. - Truy vấn "
1 5 A". Trước là "AABDZ", nay là "AABDA". - Truy vấn "
3 2 4". Xâu: "AABDA". Xâu con $t[2..4]$ = "ABD", đáp án: 0. Sau khi sắp xếp "ABD" không đổi, xâu vẫn là "AABDA". - Truy vấn "
2 1 5". Xâu: "AABDA". Xâu con "AABDA", đáp án: 7. Xâu không thay đổi. - Truy vấn "
1 1 C". Trước là "AABDA", nay là "CABDA". - Truy vấn "
2 1 2". Xâu: "CABDA". Xâu con $t[1..2]$ = "CA", đáp án: 1. Xâu không thay đổi. - Truy vấn "
3 4 5". Xâu: "CABDA". Xâu con $t[4..5]$ = "DA", đáp án: 1. Sau khi biến đổi: "DA" $\rightarrow$ "AD". Xâu trở thành "CABAD". - Truy vấn "
2 3 5". Xâu: "CABAD". Xâu con $t[3..5]$ = "BAD", đáp án: 1. Xâu không thay đổi. - Truy vấn "
1 2 B". Trước là "CABAD", nay là "CBBAD". - Truy vấn "
2 1 5". Xâu: "CBBAD". Xâu con "CBBAD", đáp án: 9. Xâu không thay đổi. - Truy vấn "
3 1 1". Xâu: "CBBAD". Xâu con $t[1..1]$ = "C", đáp án: 0. Sắp xếp độ dài 1 không làm thay đổi gì, xâu vẫn là "CBBAD". - Truy vấn "
2 1 1". Xâu: "CBBAD". Xâu con $t[1..1]$ = "C", đáp án: 0. Xâu không thay đổi. - Truy vấn "
1 4 D". Trước là "CBBAD", nay là "CBBDD". - Truy vấn "
2 1 5". Xâu: "CBBDD". Xâu con $t[1..5]$ = "CBBDD", đáp án: 3. Xâu không thay đổi. - Truy vấn "
3 1 5". Xâu: "CBBDD". Xâu con $t[1..5]$ = "CBBDD", đáp án: 3. Sau khi biến đổi: "CBBDD" $\rightarrow$ "BBCDD". Xâu cuối cùng là "BBCDD".