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.")