当前没有测试数据。

题面翻译

给你一个长为 $n$ 的字符串，只包含 abc 三种字符。$q$ 次操作，每次把一个位置的字符改成给定字符，询问当前串至少修改几次满足不包含子串 abc。修改指把一个位置的字符修改成 a、b、c 三种字符之一。

$1\le n,q\le 10^5$。

题目描述

在成为一名成功的交易员之前，威廉获得了大学学位。在他的求学期间，发生了一件有趣的事情，此后威廉开始更加专注地聆听作业任务。以下是作业任务的正确正式描述： 给定一个长度为 n 仅由字符“a”、“b”和“c”组成的字符串 s 。有 q 次查询，格式为（pos,c），意味着将字符串 s 中位置为 pos 的元素替换为字符 c 。每次查询后，您必须输出字符串中必须被替换的最小字符数量，以使字符串不包含子串“abc”。有效的字符替换是将其替换为“a”、“b”或“c”。如果字符串 x 可以通过从字符串 y 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符而得到，则字符串 x 是字符串 y 的子串。

输入格式

第一行包含两个整数 $n$ and $q$ $(1 \le n, q \le 10^5)$ , 分别为字符串的长度和查询的数量。

第二行包含字符串 s ，由字符“a”、“b”和“c”组成。

接下来的 $q$ 行中的每一行都包含一个整数 $i$ 和字符 $c$ $(1 \le i \le n)$ , 分别为字符串中的索引和新元素的值。保证字符 c 的值为“a”、“b”或“c”。

输出格式

对于每个查询，输出必须被替换的最少字符数，以使字符串不包含“abc”作为子串。

样例 #1

样例输入 #1

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

样例输出 #1

3
2
2
2
1
2
1
1
1
0

提示

Let's consider the state of the string after each query:

1. $s =$ "abcabcabc". In this case $3$ replacements can be performed to get, for instance, string $s =$ "bbcaccabb". This string does not contain "abc" as a substring.
2. $s =$ "bbcabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bbcbbcbbc". This string does not contain "abc" as a substring.
3. $s =$ "bccabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bccbbcbbc". This string does not contain "abc" as a substring.
4. $s =$ "bcaabcabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bcabbcbbc". This string does not contain "abc" as a substring.
5. $s =$ "bcabbcabc". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcabb". This string does not contain "abc" as a substring.
6. $s =$ "bcabccabc". In this case $2$ replacements can be performed to get, for instance, string $s =$ "bcabbcabb". This string does not contain "abc" as a substring.
7. $s =$ "bcabccaac". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcaac". This string does not contain "abc" as a substring.
8. $s =$ "bcabccaab". In this case $1$ replacements can be performed to get, for instance, string $s =$ "bcabbcaab". This string does not contain "abc" as a substring.
9. $s =$ "ccabccaab". In this case $1$ replacements can be performed to get, for instance, string $s =$ "ccabbcaab". This string does not contain "abc" as a substring.
10. $s =$ "ccaaccaab". In this case the string does not contain "abc" as a substring and no replacements are needed.