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"。