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

题目描述

强哥的黑板上有一个字符串 S，长度为 $N$。接下来强哥会提出 Q 个问题，需要小z来依次处理，可是小z不会做这道题，只好来求助班级里的小华同学，~~~~毕竟月赛拿下了满分👍 。

对于第 i 个问题：

• 首先给定一个整数 X[i] 和一个字符 C[i]，然后将 S 的第 X[i] 个字符替换为 C[i]。最后需要输出字符串 S 中包含 "ABC" 作为子串的次数。

这里，S 的 子串 指的是，从 S 的开头删除 0 个或多个字符，从 S 的结尾删除 0 个或多个字符后得到的字符串。

例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

• N Q
• S
• X1 C1
• X2 C2
• ...
• XQ CQ

数据范围

• $3≤N≤2×10^5，1≤Q≤2×10^5$
• S 是由大写字母组成的长度为 N 的字符串
• 1≤Xi≤N
• Ci 是大写字母

输出格式

输出 Q 行。第 i 行 (1≤i≤Q) 包含第 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

提示

示例解释 1

处理每个查询后的 S 如下：

• 处理第 1 个查询后：S 变为 ABCBABC。其中 ABC 作为子串出现了 2 次。
• 处理第 2 个查询后：S 变为 ABABABC。其中 ABC 作为子串出现了 1 次。
• 处理第 3 个查询后：S 变为 ABABCBC。其中 ABC 作为子串出现了 1 次。
• 处理第 4 个查询后：S 变为 ABAGCBC。其中 ABC 作为子串出现了 0 次。

示例解释 2

有时处理查询前后 S 可能不会发生变化。