题目描述

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

对于第 $i$ 个查询：

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

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

例如，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$ 个查询的答案。

样例 1

输入

7 4
ABCDABC
4 B
3 A
5 C
4 G

输出

2
1
1
0

样例 2

输入

3 3
ABC
1 A
2 B
3 C

输出

1
1
1

样例 3

输入

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×10^5$
• $1 \le Q \le 2×10^5$
• $S$ 是由大写字母组成的长度为 $N$ 的字符串
• $1 \le Xi \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$ 次。

示例解释 2

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