该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $n$ 的字符串 $S$，你需要依次处理 $q$ 次询问。

第 $i$ 次询问如下：

• 给定一个整数 $x_i$ 和一个字符 $c_i$，将 $s$ 的第 $x_i$ 个字符替换为 $c_i$。然后，输出字符串 ABC 作为 $s$ 的子串出现的次数。

子串是通过从字符串的开头删除零个或多个字符并从结尾删除零个或多个字符得到的字符串。例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

第一行两个正整数 $n$ 和 $q$, 分别代表字符串的长度和询问次数。（$3 \le n \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$)

第二行为一个长度为 $n$ 的字符串 $s$. ($s$ 仅由大写英文字母组成)

接下来 $q$ 行，每行有一个正整数 $x_i$ 和一个字符 $c_i$.（$1 \le x_i \le n$, $c_i$ 为一个大写英文字母)

输出格式

输出 $q$ 行。第 $i$ 行应包含第 $i$ 次询问的答案。

样例

7 4
ABCDABC
4 B
3 A
5 C
4 G

2
1
1
0

3 3
ABC
1 A
2 B
3 C

1
1
1

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

样例解释

对于样例 1，每次询问后， $s$为:

1. $s = ABCBABC$. 子串 ABC 出现 $2$ 次.
2. $s = ABABABC$. 子串 ABC 出现 $1$ 次
3. $s = ABABCBC$. 子串 ABC 出现 $1$ 次
4. $s = ABAGCBC$. 子串 ABC 出现 $0$ 次