← 返回题目列表

Codeforces · 570/C

C. 更换

中文机器翻译题面 查看原题

Daniel 有一个字符串 s,由小写英文字母和句号(字符“.”)组成。让我们将替换操作定义为以下步骤序列:在字符串 s 中找到子字符串“..”(两个连续的句点),在该子字符串的所有出现中选择第一个,并将该子字符串替换为字符串“.”。也就是说,在替换操作时,前两个连续的周期被替换为一个。如果字符串 s 不包含两个连续的句点,则不会发生任何事情。

让我们将 f(s) 定义为要执行的替换操作的最少次数,这样字符串就不会剩下任何两个连续的句点。

您需要处理 m 个查询,第 i 个查询结果是字符串 s 的位置 xi (1 ≤ xi ≤ n) 处的字符被赋值为 ci。每次操作后,您必须计算并输出 f(s) 的值。

帮助 Daniel 处理所有查询。

输入

第一行包含两个整数n和m(1≤n,m≤300000)字符串的长度和查询的次数。

第二行包含字符串s,由n个小写英文字母和句号组成。

以下 m 行包含查询的描述。第i行包含整数xi和ci(1≤xi≤n,ci——小写英文字母或句点符号),描述将符号ci分配给位置xi的查询。

输出

打印 m 个数字,每行一个,这些数字中的第 i 个数字必须等于执行第 i 次赋值后 f(s) 的值。

示例

输入 #1

10 3
.b..bz....
1 h
3 c
9 f

输出 #1

4
3
1

输入 #2

4 4
.cc.
2 .
3 .
2 a
1 a

输出 #2

1
3
1
1

注意

第一个样本测试的注释(替换的句点括在方括号中)。

原始字符串是“.b..bz....”。

- 第一个查询后 f(hb..bz....) = 4    ("hb[..]bz...."  →  "hb.bz[..].."  →  "hb.bz[..]."  →  "hb.bz[..]"  → “hb.bz。”)
- 第二次查询后 f(hbс.bz....) = 3    ("hbс.bz[..].."  →  "hbс.bz[..]."  →  "hbс.bz[..]"  →  "hbс.bz.")
- 第三次查询后 f(hbс.bz..f.) = 1    ("hbс.bz[..]f."  →  "hbс.bz.f.")

第二个样本测试注意事项。

原始字符串是“.cc.”。

- 第一个查询之后: f(..c.) = 1    ("[..]c."  →  ".c.")
- 第二次查询后: f(....) = 3    ("[..].."  →  "[..]."  →  "[..]"  →  ".")
- 第三次查询后: f(.a..) = 1    (".a[..]"  →  ".a.")
- 第四个查询之后: f(aa..) = 1    ("aa[..]"  →  "aa.")