Cleopatra 喜歡字串。當她拿到一個長度為 $n$ 的字串 $s$(由字元 $s[1], \dots, s[n]$ 組成)時,她會立即開始對其進行排序。在排序過程中,她會執行一系列形如 $s[i] \leftrightarrow s[i + 1]$ 的交換操作,其中 $i \in \{1, 2, \dots, n - 1\}$。最後,她會傳回排序後的字串,並索取等同於所有執行過的交換操作中 $i$ 的總和之金幣數量(如果同一個 $i$ 進行了多次交換,則該 $i$ 將在總和中被計算相對應的次數)。Cleopatra 並不浪費:在所有可以對字串進行排序的方法中,她會選擇使她獲得的金幣數量最少的那一種。
Catherine de' Medici 也喜歡字串。她有一個長度為 $n$ 的字串,並且想用它來玩遊戲。具體來說,她對以下操作感興趣:
- "
1 i c" —— 將 $s[i]$ 替換為 $c$; - "
2 i j" —— 複製字串 $s$ 中從第 $i$ 個到第 $j$ 個字元(含)的子字串($i \le j$)並對其進行排序,而字串 $s$ 的字元保持不變。 - "
3 i j" —— 取出字串 $s$ 中從第 $i$ 個到第 $j$ 個字元(含)的子字串($i \le j$),對其進行排序,然後將其插回字串 $s$ 的相同位置。
Catherine de' Medici 可以自己處理第一種類型的詢問,但第二種和第三種類型的詢問太複雜了,她會去找 Cleopatra 幫忙。在評估此過程的費用時,Cleopatra 累加的不是字串 $s$ 中的索引(從 $i$ 到 $j$),而是相對於子字串開頭的索引(從 $1$ 到 $j - i + 1$)。
Catherine de' Medici 同樣不浪費,並且仔細監控著她的預算。因此,對於她向 Cleopatra 提出的每個請求,請計算 Catherine de' Medici 需要花費多少枚金幣。
輸入格式
輸入的第一行包含一個整數 $t$ —— 測試資料的組數($1 \le t \le 3 \cdot 10^5$)。對於每組測試資料:
第一行包含兩個整數 $n$ 和 $q$ —— 字串的長度和詢問的數量($1 \le n, q \le 3 \cdot 10^5$)。下一行包含一個由 $n$ 個大寫英文字母組成的字串。接下來的 $q$ 行描述詢問。每個詢問的描述為以下三種類型之一:
- "
1 i c" —— 將 $s[i]$ 替換為 $c$($1 \le i \le n$; $c \in \{\text{A}, \text{B}, \dots, \text{Z}\}$); - "
2 i j" —— 求對子字串 $s[i..j]$ 進行排序的費用,同時字串 $s$ 保持不變($1 \le i, j \le n$); - "
3 i j" —— 求對子字串 $s[i..j]$ 進行排序的費用,同時字串 $s$ 中的子字串 $s[i..j]$ 被替換為排序後的子字串($1 \le i, j \le n$)。
在每組測試資料中,將至少包含一個第二種或第三種類型的詢問。
所有測試資料中 $n$ 的總和不超過 $3 \cdot 10^5$。所有測試資料中 $q$ 的總和不超過 $3 \cdot 10^5$。
輸出格式
對於每組測試資料,在單獨的一行中輸出所有第二種和第三種類型詢問的答案,即 Cleopatra 每次排序將獲得的金幣數量。
範例
範例輸入 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
範例輸出 1
18 3 1 16 0 0 7 1 1 1 9 0 0 3 3
範例輸入 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
範例輸出 2
4 4 0 0 0 9 9 0 0 3 1 1
說明
考慮第一個範例。在其中,初始字串為 "DBCAA"。讓我們按順序查看所有 20 個詢問:
- 詢問 "
2 1 5". 當前字串: "DBCAA". 子字串 $t[1..5]$ = "DBCAA", 答案: 18. 字串不改變。 - 詢問 "
2 2 4". 字串: "DBCAA". 子字串 $t[2..4]$ = "BCA", 答案: 3. 字串不改變。 - 詢問 "
1 3 Z". 更新: $t[3] \leftarrow$ "Z". 原為 "DBCAA",現為 "DBZAA"。 - 詢問 "
2 1 3". 字串: "DBZAA". 子字串 $t[1..3]$ = "DBZ", 答案: 1. 字串不改變。 - 詢問 "
3 1 5". 字串: "DBZAA". 子字串 $t[1..5]$ = "DBZAA", 答案: 16. 變化後,對子字串進行排序:"DBZAA" $\rightarrow$ "AABDZ"。字串變為 "AABDZ"。 - 詢問 "
2 1 5". 字串: "AABDZ". 子字串 "AABDZ", 答案: 0. 字串不改變。 - 詢問 "
1 5 A". 原為 "AABDZ",現為 "AABDA"。 - 詢問 "
3 2 4". 字串: "AABDA". 子字串 $t[2..4]$ = "ABD", 答案: 0. 排序後 "ABD" 不改變,字串保持為 "AABDA"。 - 詢問 "
2 1 5". 字串: "AABDA". 子字串 "AABDA", 答案: 7. 字串不改變。 - 詢問 "
1 1 C". 原為 "AABDA",現為 "CABDA"。 - 詢問 "
2 1 2". 字串: "CABDA". 子字串 $t[1..2]$ = "CA", 答案: 1. 字串不改變。 - 詢問 "
3 4 5". 字串: "CABDA". 子字串 $t[4..5]$ = "DA", 答案: 1. 變化後:"DA" $\rightarrow$ "AD"。字串變為 "CABAD"。 - 詢問 "
2 3 5". 字串: "CABAD". 子字串 $t[3..5]$ = "BAD", 答案: 1. 字串不改變。 - 詢問 "
1 2 B". 原為 "CABAD",現為 "CBBAD"。 - 詢問 "
2 1 5". 字串: "CBBAD". 子字串 "CBBAD", 答案: 9. 字串不改變。 - 詢問 "
3 1 1". 字串: "CBBAD". 子字串 $t[1..1]$ = "C", 答案: 0. 對長度為 1 的子字串進行排序不會改變任何內容,字串保持為 "CBBAD"。 - 詢問 "
2 1 1". 字串: "CBBAD". 子字串 $t[1..1]$ = "C", 答案: 0. 字串不改變。 - 詢問 "
1 4 D". 原為 "CBBAD",現為 "CBBDD"。 - 詢問 "
2 1 5". 字串: "CBBDD". 子字串 $t[1..5]$ = "CBBDD", 答案: 3. 字串不改變。 - 詢問 "
3 1 5". 字串: "CBBDD". 子字串 $t[1..5]$ = "CBBDD", 答案: 3. 變化後:"CBBDD" $\rightarrow$ "BBCDD"。最終字串為 "BBCDD"。