时间限制：2 sec

空间限制：1024 MB

题目描述

给定一个长度为 $N$ 的字符串 $S$。还给出 $Q$ 个询问，你需要处理每个询问并输出结果。

每个询问定义如下：

• 给定一个索引 $i$ 和一个字符 $C_i$，将 $S$ 的第 $i$ 个字符替换为 $C_i$。然后，计算 $S$ 中有多少个子串等于 "ABC"。

注意，子串 $T$ 是连续的，或者说通过从原始字符串中删除零个或多个字符（从两端或中间）而得到的字符串。例如，"ab" 是 "abc" 的子串，而 "ac" 不是。

约束条件

• $3 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ 是一个长度为 $N$ 的由大写写英文字母组成的字符串
• $1 \leq i \leq N$
• $C_i$ 是大写英文字母

输入格式

输入按以下格式从标准输入给出：

$N$   $Q$

$S$

$i_1$   $C_1$

$i_2$   $C_2$

$\vdots$

$i_Q$   $C_Q$

输出格式

对于每个询问，输出 $S$ 中子串 "ABC" 的数量。

样例

样例1

7 4
ABCDABC
4 B
3 A
5 C
4 G

2
1
1
0

处理完每个查询后， S 变为如下形式。

第一次查询后： S= ABCBABC 。在此字符串中， ABC 作为子字符串出现了两次。

第二次查询后： S= ABABABC 。在此字符串中， ABC 作为子字符串出现一次。

第三次查询后： S= ABABCBC 。在此字符串中， ABC 作为子字符串出现一次。

第四次查询后： S= ABAGCBC 。在此字符串中， ABC 作为子字符串出现零次。

样例2

3 3
ABC
1 A
2 B
3 C

1
1
1

样例3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

0
0
0
0
1
1
2
2
1
1