CF1609B.William the Vigilant

Before becoming a successful trader William got a university degree. During his education an interesting situation happened, after which William started to listen to homework assignments much more attentively. What follows is the correct formal description of the homework assignment:

You are given a string $s$ of length $n$ only consisting of characters "a", "b" and "c". There are $q$ queries of format ($pos, c$), meaning replacing the element of string $s$ at position $pos$ with character $c$. After each query you must output the minimal number of characters in the string, which have to be replaced, so that the string doesn't contain string "abc" as a substring. A valid replacement of a character is replacing it with "a", "b" or "c".

A string $x$ is a substring of a string $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

在成为一名成功的交易员之前，威廉曾获得大学学位。求学期间发生了一件有趣的事情，此后威廉便开始更加认真地听讲作业要求。以下是该作业题目的准确形式化描述：

给定一个长度为 $n$ 的字符串 $s$，其中仅包含字符 "a"、"b" 和 "c"。共有 $q$ 个查询，每个查询的格式为 ($pos, c$)，表示将字符串 $s$ 中位置 $pos$ 处的字符替换为字符 $c$。每次查询后，你必须输出：为使字符串中不包含子串 "abc"，所需修改的最少字符个数。每次修改操作只能将某个字符替换为 "a"、"b" 或 "c" 中的一个。

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

The first line contains two integers $n$ and $q$ $(1 \le n, q \le 10^5)$, the length of the string and the number of queries, respectively.

The second line contains the string $s$, consisting of characters "a", "b" and "c".

Each of the next $q$ lines contains an integer $i$ and character $c$ $(1 \le i \le n)$, index and the value of the new item in the string, respectively. It is guaranteed that character's $c$ value is "a", "b" or "c".

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

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

接下来的 $q$ 行中，每行包含一个整数 $i$ 和一个字符 $c$ $(1 \le i \le n)$，分别表示字符串中要更新的位置（下标从 1 开始）以及该位置的新字符。保证字符 $c$ 的值为 "a"、"b" 或 "c"。

For each query output the minimal number of characters that would have to be replaced so that the string doesn't contain "abc" as a substring.

对于每个查询，输出最少需要替换的字符数量，使得字符串中不包含子串 "abc"。

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.

我们考虑每次查询后字符串的状态：

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"，无需执行任何替换操作。