Клеопатра любить рядки. Коли їй дають рядок $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".