クレオパトラは文字列が大好きです。長さ $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$ の同じ位置に戻す。
カトリーヌ・ド・メディシスは1番目の種類のクエリは自分で処理できますが、2番目と3番目の種類のクエリは複雑すぎるため、クレオパトラに依頼します。この手続きのコストを評価する際、クレオパトラは文字列 $s$ におけるインデックス($i$ から $j$)ではなく、部分文字列の先頭からの相対的なインデックス($1$ から $j - i + 1$)の和をとります。
カトリーヌ・ド・メディシスも無駄遣いをせず、予算を注意深く管理しています。したがって、彼女がクレオパトラに行う各依頼について、カトリーヌ・ド・メディシスが支払わなければならない金貨の枚数を計算してください。
入力
入力の最初の行には、テストケースの数を表す整数 $t$($1 \le t \le 3 \cdot 10^5$)が与えられます。各テストケースについて:
最初の行には、文字列の長さとクエリの数を表す2つの整数 $n$ と $q$($1 \le n, q \le 3 \cdot 10^5$)が与えられます。次の行には、$n$ 個の英大文字からなる文字列が与えられます。続く $q$ 行にはクエリが記述されます。各クエリの記述は以下の3種類のいずれかです:
- "
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$)。
各テストケースには、2番目または3番目の種類のクエリが少なくとも1つ含まれます。
すべてのテストケースにおける $n$ の総和は高々 $3 \cdot 10^5$ です。すべてのテストケースにおける $q$ の総和は高々 $3 \cdot 10^5$ です。
出力
各テストケースについて、2番目および3番目の種類のすべてのクエリに対する答え、すなわち各ソートに対してクレオパトラが受け取る金貨の枚数をそれぞれ改行区切りで出力してください。
入出力例
入力例 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" です。