클레오파트라는 문자열을 좋아합니다. 길이 $n$인 문자열 $s$(문자 $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$는 그대로 두고, 부분 문자열 $s[i..j]$를 정렬하는 비용을 구합니다 ($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$입니다.
출력
각 테스트 케이스마다 두 번째와 세 번째 유형의 모든 쿼리에 대한 답, 즉 각 정렬에 대해 클레오파트라가 받게 될 금화의 개수를 각 줄에 하나씩 출력합니다.
예제
예제 입력 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"입니다.