William The Oblivious

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的字符串 $s$，它仅由字符 a、b 和 c 组成。

有 $q$ 次修改。每次修改给出位置 $pos$ 和字符 $c$，表示把 $s$ 的第 $pos$ 个字符替换为 $c$。每次修改后，请求出至少还要替换多少个字符，才能使字符串中不包含 abc 作为子序列。一次合法替换可以把某个字符替换为 a、b 或 c。

如果字符串 $x$ 可以通过从字符串 $y$ 中删除若干字符，并保持其余字符的相对顺序不变而得到，则称 $x$ 是 $y$ 的子序列。

输入格式

第一行包含两个整数 $n,q$。

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

接下来 $q$ 行，每行包含一个整数 $pos$ 和一个字符 $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\le n,q\le10^5$；
• $1\le pos\le n$；
• $s$ 和每次修改中的字符均属于 $\{a,b,c\}$。

本题采用独立测试点计分。