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