再数 ABC

题目描述

给你一个长度为 $N$ 的字符串 $S$，以及需要按顺序处理的 $Q$ 个查询。

第 $i$ 个查询如下：

给定整数 $X_i$ 和字符 $C_i$，将 $S$ 中第 $X_i$ 个字符替换为 $C_i$。然后，输出 $S$ 中作为子串出现的 ABC 的次数。

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

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

输入格式

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

$N$ $Q$
$S$
$X_1$ $C_1$
$X_2$ $C_2$
$\vdots$
$X_Q$ $C_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行 $(1 \le i \le Q)$ 应包含第 $i$ 个查询的答案。

样例

7 4
ABCDABC
4 B
3 A
5 C
4 G

2
1
1
0

每次查询处理完毕后，$S$ 变为：

第一次查询后：$S=$ ABCBABC。该字符串中，ABC 作为子串出现了 2 次。

第二次查询后：$S=$ ABABABC。该字符串中，ABC 作为子串出现了 1 次。

第三次查询后：$S=$ ABABCBC。该字符串中，ABC 作为子串出现了 1 次。

第四次查询后：$S=$ ABAGCBC。该字符串中，ABC 作为子串出现了 0 次。

3 3
ABC
1 A
2 B
3 C

1
1
1

也有处理某个查询时 $S$ 不变的情况。

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$ 是大写英文字母