在成为一名成功的交易员之前,威廉获得了大学学位。在他的教育过程中,发生了一个有趣的情况,之后威廉开始更加专心地听作业。以下是威廉听到的家庭作业的正式描述:
给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符“a”、“b”和“c”。存在格式为 ($$$pos, c$$$) 的 $$$q$$$ 查询,表示将 $$$s$$$ 位置 $$$pos$$$ 处的元素替换为字符 $$$c$$$。每次查询后,您必须输出字符串中必须替换的最少字符数,以便字符串不包含字符串“abc”作为子序列。字符的有效替换是将其替换为“a”、“b”或“c”。
如果可以通过删除一些字符而不改变剩余字符的顺序从 $$$y$$$ 获得 $$$x$$$,则字符串 $$$x$$$ 被称为字符串 $$$y$$$ 的子序列。
输入
第一行包含两个整数 $$$n$$$ 和 $$$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
9 12 aaabccccc 4 a 4 b 2 b 5 a 1 b 6 b 5 c 2 a 1 a 5 a 6 b 7 b
输出 #1
0 1 2 2 1 2 1 2 2 2 2 2
注意
让我们考虑一下每次查询后字符串的状态:
1. $$$s = $$$"aaaaccccc"。在这种情况下,字符串不包含“abc”作为子序列,并且不需要替换。
2. $$$s = $$$"aaabccccc"。在这种情况下,可以执行 1 次替换以获得字符串 $$$s = $$$"aaaaccccc"。该字符串不包含“abc”作为子序列。
3. $$$s = $$$"ababccccc"。在这种情况下,可以执行 2 次替换来得到,例如字符串 $$$s = $$$aaaacccccc"。该字符串不包含“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 = $$$"bbbbbcbccc"。该字符串不包含“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 = $$$"aaabbabbbb"。该字符串不包含“abc”作为子序列。