103722: [Atcoder]ABC372 C - Count ABC Again

Problem Statement

You are given a string $S$ of length $N$. You are also given $Q$ queries, which you should process in order.

The $i$-th query is as follows:

• Given an integer $X_i$ and a character $C_i$, replace the $X_i$-th character of $S$ with $C_i$. Then, print the number of times the string ABC appears as a substring in $S$.

Here, a substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• $3 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ is a string of length $N$ consisting of uppercase English letters.
• $1 \le X_i \le N$
• $C_i$ is an uppercase English letter.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line $(1 \le i \le Q)$ should contain the answer to the $i$-th query.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, $S$ becomes as follows.

• After the first query: $S=$ ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: $S=$ ABABABC. In this string, ABC appears once as a substring.
• After the third query: $S=$ ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: $S=$ ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where $S$ does not change through processing a query.

Sample Input 3

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

Sample Output 3

0
0
0
0
1
1
2
2
1
1

问题陈述

给你一个长度为$N$的字符串$S$。还给你$Q$个查询，你应该按顺序处理它们。

第$i$个查询如下：

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

在这里，$S$的子字符串是通过从$S$的开头删除零个或多个字符以及从$S$的末尾删除零个或多个字符获得的字符串。
例如，ab是abc的子字符串，但ac不是abc的子字符串。

约束条件

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

输入

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

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

输出

打印$Q$行。 第$i$行（$1 \le i \le Q$）应包含对第$i$个查询的答案。

示例输入 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

示例输出 1

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

示例输出 2

1
1
1

有些情况下，通过处理查询$S$不会发生变化。

示例输入 3

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

示例输出 3

0
0
0
0
1
1
2
2
1
1