CF1609E.William The Oblivious

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 a formal description of the homework assignment as William heard it:

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 subsequence. A valid replacement of a character is replacing it with "a", "b" or "c".

A string $x$ is said to be a subsequence of string $y$ if $x$ can be obtained from $y$ by deleting some characters without changing the ordering of the remaining characters.

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

给定一个长度为 $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 subsequence.

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

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

1. $s = $"aaaaccccc". In this case the string does not contain "abc" as a subsequence and no replacements are needed.
2. $s = $"aaabccccc". In this case 1 replacements can be performed to get, for instance, string $s = $"aaaaccccc". This string does not contain "abc" as a subsequence.
3. $s = $"ababccccc". In this case 2 replacements can be performed to get, for instance, string $s = $aaaaccccc". This string does not contain "abc" as a subsequence.
4. $s = $"ababacccc". In this case 2 replacements can be performed to get, for instance, string $s = $"aaaaacccc". This string does not contain "abc" as a subsequence.
5. $s = $"bbabacccc". In this case 1 replacements can be performed to get, for instance, string $s = $"bbacacccc". This string does not contain "abc" as a subsequence.
6. $s = $"bbababccc". In this case 2 replacements can be performed to get, for instance, string $s = $"bbacacccc". This string does not contain "abc" as a subsequence.
7. $s = $"bbabcbccc". In this case 1 replacements can be performed to get, for instance, string $s = $"bbcbcbccc". This string does not contain "abc" as a subsequence.
8. $s = $"baabcbccc". In this case 2 replacements can be performed to get, for instance, string $s = $"bbbbcbccc". This string does not contain "abc" as a subsequence.
9. $s = $"aaabcbccc". In this case 2 replacements can be performed to get, for instance, string $s = $"aaacccccc". This string does not contain "abc" as a subsequence.
10. $s = $"aaababccc". In this case 2 replacements can be performed to get, for instance, string $s = $"aaacacccc". This string does not contain "abc" as a subsequence.
11. $s = $"aaababccc". In this case 2 replacements can be performed to get, for instance, string $s = $"aaacacccc". This string does not contain "abc" as a subsequence.
12. $s = $"aaababbcc". In this case 2 replacements can be performed to get, for instance, string $s = $"aaababbbb". This string does not contain "abc" as a subsequence.

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

1. $s = $"aaaaccccc"。此时字符串不包含 "abc" 作为子序列，无需进行任何替换。
2. $s = $"aaabccccc"。此时可执行 1 次替换，例如得到字符串 $s = $"aaaaccccc"。该字符串不包含 "abc" 作为子序列。
3. $s = $"ababccccc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaaaccccc"。该字符串不包含 "abc" 作为子序列。
4. $s = $"ababacccc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaaaacccc"。该字符串不包含 "abc" 作为子序列。
5. $s = $"bbabacccc"。此时可执行 1 次替换，例如得到字符串 $s = $"bbacacccc"。该字符串不包含 "abc" 作为子序列。
6. $s = $"bbababccc"。此时可执行 2 次替换，例如得到字符串 $s = $"bbacacccc"。该字符串不包含 "abc" 作为子序列。
7. $s = $"bbabcbccc"。此时可执行 1 次替换，例如得到字符串 $s = $"bbcbcbccc"。该字符串不包含 "abc" 作为子序列。
8. $s = $"baabcbccc"。此时可执行 2 次替换，例如得到字符串 $s = $"bbbbcbccc"。该字符串不包含 "abc" 作为子序列。
9. $s = $"aaabcbccc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaacccccc"。该字符串不包含 "abc" 作为子序列。
10. $s = $"aaababccc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaacacccc"。该字符串不包含 "abc" 作为子序列。
11. $s = $"aaababccc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaacacccc"。该字符串不包含 "abc" 作为子序列。
12. $s = $"aaababbcc"。此时可执行 2 次替换，例如得到字符串 $s = $"aaababbbb"。该字符串不包含 "abc" 作为子序列。