1522 - Douteki Programming

問題

文字列$\ S \ $について 1165 - ハッピー文字列YDK の答えを返す関数を$\ YDK(S) \ $とする。すなわち、$\ YDK($YDKYDK$) \ = 4 \ $である。

あなたは長さ$\ N \ $の文字列$\ S \ $を所持しており、この文字列に対して以下のような更新クエリが$\ Q \ $回にわたって与えられる。各更新後の文字列$\ S \ $について、$YDK(S) \ $を求めよ。

$i \ $回目のクエリでは整数$\ l_i,r_i \ $及び文字$\ c_i \ $が与えられ、意味は次の通りである。

• $S \ $の$\ l_i \ $文字目から$\ r_i \ $文字目までを文字$\ c_i \ $に置き換える。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$S$
$l_1 \ r_1 \ c_1$
$l_2 \ r_2 \ c_2$
$\vdots$
$l_Q \ r_Q \ c_Q$

出力

出力は$\ Q \ $行からなり、$i \ $行目には$\ i \ $番目までの更新を行った後の文字列$\ S \ $について$\ YDK(S) \ $を出力せよ。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N,Q \leq 2 \times 10^5$
• $S \ $は英大文字のみからなる長さ$\ N \ $の文字列
• $1 \leq l_i \leq r_i \leq N$
• $c_i \ $は英大文字

入出力例

入力例1

6 3
YYDDDD
5 6 K
1 4 Y
5 5 D

出力例1

8
0
4

• 1回目:$\ S =$YYDDKK なので8
• 2回目:$\ S =$YYYYKK なので0
• 3回目:$\ S =$YYYYDK なので4

---

入力例2

8 5
YDKKDYKK
4 8 C
6 8 K
7 7 D
2 5 Y
3 4 N

出力例2

1
4
4
5
3