题目描述

在成为一名成功的交易员之前，William 获得了大学学位。在他的求学过程中，发生了一件有趣的事情，从那以后，William 开始更加认真地听作业要求。以下是作业的正式描述：

给定一个长度为 $n$ 的字符串 $s$，仅由字符 "a"、"b" 和 "c" 组成。有 $q$ 个操作，每个操作为 $(pos, c)$，表示将字符串 $s$ 的第 $pos$ 个字符替换为字符 $c$。每次操作后，你需要输出最少需要替换多少个字符，才能使字符串中不再包含子串 "abc"。一次合法的替换可以将某个字符替换为 "a"、"b" 或 "c"。

如果字符串 $x$ 可以通过从字符串 $y$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到，则称 $x$ 是 $y$ 的子串。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示字符串的长度和操作次数，满足 $1 \le n, q \le 10^5$。

第二行包含字符串 $s$，仅由字符 "a"、"b" 和 "c" 组成。

接下来的 $q$ 行，每行包含一个整数 $i$ 和一个字符 $c$，表示将第 $i$ 个字符替换为字符 $c$，其中 $1 \le i \le n$，$c$ 只能是 "a"、"b" 或 "c"。

输出格式

对于每个操作，输出一个整数，表示最少需要替换多少个字符，才能使字符串中不再包含子串 "abc"。

说明/提示

我们来考虑每次操作后的字符串状态：

1. $s =$ "abcabcabc"。此时可以进行 $3$ 次替换，例如变为 $s =$ "bbcaccabb"。该字符串不包含 "abc" 作为子串。
2. $s =$ "bbcabcabc"。此时可以进行 $2$ 次替换，例如变为 $s =$ "bbcbbcbbc"。该字符串不包含 "abc" 作为子串。
3. $s =$ "bccabcabc"。此时可以进行 $2$ 次替换，例如变为 $s =$ "bccbbcbbc"。该字符串不包含 "abc" 作为子串。
4. $s =$ "bcaabcabc"。此时可以进行 $2$ 次替换，例如变为 $s =$ "bcabbcbbc"。该字符串不包含 "abc" 作为子串。
5. $s =$ "bcabbcabc"。此时可以进行 $1$ 次替换，例如变为 $s =$ "bcabbcabb"。该字符串不包含 "abc" 作为子串。
6. $s =$ "bcabccabc"。此时可以进行 $2$ 次替换，例如变为 $s =$ "bcabbcabb"。该字符串不包含 "abc" 作为子串。
7. $s =$ "bcabccaac"。此时可以进行 $1$ 次替换，例如变为 $s =$ "bcabbcaac"。该字符串不包含 "abc" 作为子串。
8. $s =$ "bcabccaab"。此时可以进行 $1$ 次替换，例如变为 $s =$ "bcabbcaab"。该字符串不包含 "abc" 作为子串。
9. $s =$ "ccabccaab"。此时可以进行 $1$ 次替换，例如变为 $s =$ "ccabbcaab"。该字符串不包含 "abc" 作为子串。
10. $s =$ "ccaaccaab"。此时字符串中不包含 "abc" 作为子串，无需替换。

由 ChatGPT 4.1 翻译

样例

9 10
abcabcabc
1 a
1 b
2 c
3 a
4 b
5 c
8 a
9 b
1 c
4 a

3
2
2
2
1
2
1
1
1
0