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

题目描述

给定一个长度为 $N$ 的字符串 $S$，接着给出 $Q$ 个查询，依次处理。

对于第 $i$ 个查询：

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

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

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

输入格式

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

输出格式

输出 $Q$ 行。第 $i$ 行 $(1 \le i \le 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

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

数据约束

• $3 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ 是由大写字母组成的长度为 $N$ 的字符串
• $1 \le X_i \le N$
• $C_i$ 是大写字母

样例解释

• 样例 1：处理每个查询后的 $S$ 如下：

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