注意

C++での想定解コードは約 $\mathrm{650ms}$、PyPy3での想定解コードは約 $\mathrm{4500ms}$ です。

高速な言語を使用することを強く推奨します。低速な言語の場合は入出力高速化や非本質・非自明な定数倍高速化が求められる可能性が高いです。

問題文

文字列 $X$ が良い文字列であるというのを、以下の条件を満たすことと定義します。

• ある非負整数 $x, y, z, w$ が存在して、$X$ が$x$ 個のA、$y$ 個のB、$z$ 個のC、$w$ 個のDをこの順で連結したものと表せる

たとえば、ABCD、AABCCD、ABC、DD、空文字列などは良い文字列です。（$x, y, z, w$ は $0$ でも良いことに注意してください）

すべての文字がA、B、C、Dのいずれかからなる長さ $N$ の文字列 $S$ が与えられます。

正整数 $Q$ が与えられるので、与えられる順に $Q$ 個のクエリを処理してください。

クエリは以下の二種類のいずれかです。

• 1 x c：
  • 正整数 $x (1 \leq x \leq N)$ とA、B、C、Dのいずれかである文字 $c$ が与えられる
  • $S$ の $x$ 文字目を文字 $c$ で更新する
• 2 L R：
  • $1 \leq L \leq R \leq N$ を満たす $L, R$ が与えられるので、$S$ の $L$ 文字目から $R$ 文字目までからなる（連続）部分文字列を $T$ とする
  • $T$ に変更操作を任意の回数（$0$ 回でも良い）行って良い文字列にするときの変更操作を行う回数の最小値を出力する
  • ただし、$T$ に変更操作を行うというのを、$1 \leq i \leq |T|$ を満たす $i$ を一つ選び、$T$ の $i$ 文字目を好きな文字で変更する操作として定義します

入力

$N \ Q$
$S$ 
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各 $\mathrm{query}_i$ は、以下のいずれかの形式で与えられる。

$1\ x\ c$

$2\ L\ R$

入力は全て以下の制約を満たす。

• $1 \leq N, Q \leq 2 \times 10 ^ 5$
• $S$ は長さ $N$ の文字列
• $S$ のすべての文字はA、B、C、Dのいずれか
• $1 \leq x \leq N$
• $c$ はA、B、C、Dのいずれか
• $1 \leq L \leq R \leq N$
• $N, Q, x, L, R$ はすべて整数

出力

二つめのクエリについての答えを改行区切りで出力せよ。

サンプル

5 5
ABACD
2 2 5
1 1 D
2 1 5
1 3 D
2 1 5

1
2
2

15 15
BDBADBADBBBCBDA
2 1 7
1 5 B
1 9 D
1 5 C
2 1 13
1 3 C
2 7 8
2 1 4
1 8 A
2 3 12
2 3 7
1 8 A
1 7 D
2 7 10
2 1 13

4
7
0
2
4
3
2
8