题目描述

题目译自 USACO 2023 US Open Contest, Platinum Problem 1. Pareidolia

空想性错视是一种你的眼睛趋向于识别出图像中熟悉的图案，但这些图案实际上并不存在——例如把云看成一张脸。正如你所想象的那样，由于 FJ 经常接近奶牛，他经常在日常物品中看到与奶牛有关的图案。比如，如果他看到了字符串 bqessiyexbesszieb，FJ 的眼睛会忽略一些字母，他所看到的是 bessiebessie。

给定一个字符串 $s$，令 $B(s)$ 代表通过删除 $s$ 中的 $0$ 个或更多的字符可以形成由 bessie 不断重复的字符串中 bessie 的最大出现次数。如上例中，$B(\texttt{bqessiyexbesszieb})=2$。此外，给一个串 $t$，令 $A(t)$ 表示对于 $t$ 的所有连续子串 $s$，$B(s)$ 的和。

FJ 有一个长度至多 $2\cdot 10^5$ 且仅由小写英文字母组成的字符串 $t$。请计算 $A(t)$，并且计算在 $U\ (1\le U\le 2\cdot 10^5)$ 次修改的每一次后 $A(t)$ 的值，其中每次修改是改变 $t$ 中的一个字符。修改是累积性的。

输入格式

第一行一个字符串 $t$。

第二行一个整数 $U$，接下来 $U$ 行，每行包含一个位置 $p\ (1\le p\le N)$ 和一个小写英文字母 $c$，表示 $t$ 的第 $p$ 个字符换为 $c$。

输出格式

输出 $U+1$ 行，表示在所有修改之前和每次修改后 $A(t)$ 的值。

bessiebessie
3
3 l
7 s
3 s

14
7
1
7

数据范围与提示

• 第 2 组数据：$|t|,U\le 300$
• 3-5 组数据：$U\le 10$
• 6-13 组数据：$|t|,U\le 10^5$
• 14-21 组数据：无附加限制