Клеопатра любит строки. Когда ей дают строку $s$ длины $n$ (состоящую из символов $s[1], \dots, s[n]$), она тут же начинает её сортировать. В процессе сортировки она выполняет последовательность обменов вида $s[i] \leftrightarrow s[i + 1]$, где $i \in \{1, 2, \dots, n - 1\}$. В конце она возвращает отсортированную строку и требует количество золотых монет, равное сумме $i$ по всем сделанным обменам (если обмен с одним и тем же $i$ производился несколько раз, то это $i$ будет учтено в сумме столько раз, сколько раз производился обмен). Клеопатра не расточительна: среди всех способов отсортировать строку она выбирает тот, при котором количество монет, которое она получит за сортировку, минимально.
Екатерина Медичи тоже любит строки. У неё есть строка длины $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$ на то же самое место.
С запросами первого типа Екатерина Медичи может справиться сама, но запросы второго и третьего типов слишком сложны, и с ними она пойдёт к Клеопатре. При оценке стоимости этой процедуры Клеопатра будет суммировать не индексы из строки $s$ (от $i$ до $j$), а индексы относительно начала подстроки (от $1$ до $j - i + 1$).
Екатерина Медичи тоже не расточительна и внимательно следит за своим бюджетом. Поэтому для каждого её обращения к Клеопатре посчитайте, сколько золотых монет Екатерине Медичи придётся потратить.
Входные данные
Первая строка входных данных содержит целое число $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[i..j]$ в строке $s$ заменяется на отсортированную ($1 \le i, j \le n$).
В каждом наборе входных данных будет хотя бы один запрос второго или третьего типа.
Сумма $n$ по всем наборам входных данных не превосходит $3 \cdot 10^5$. Сумма $q$ по всем наборам входных данных не превосходит $3 \cdot 10^5$.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке ответы на все запросы второго и третьего типов, то есть количество монет, которое получит Клеопатра за каждую из сортировок.
Примеры
Входные данные 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".