空想性视错觉（Pareidolia）是一种心理现象，指人们倾向于在图像中看到并不存在的熟悉模式，例如在云朵中看到人脸。正如你所想象的那样，由于农夫约翰（Farmer John）经常与奶牛打交道，他经常在日常物品中看到与奶牛相关的模式。例如，如果他看到字符串 "bqessiyexbesszieb"，他的眼睛会忽略掉其中的一些字母，而只看到 "bessiebessie"。

给定一个字符串 $s$，令 $B(s)$ 表示通过删除 $s$ 中的零个或多个字符，所能构成的 "bessie" 的最大重复次数。在上面的例子中，$B($"bqessiyexbesszieb"$) = 2$。此外，给定一个字符串 $t$，令 $A(t)$ 表示 $t$ 的所有连续子串 $s$ 的 $B(s)$ 之和。

农夫约翰有一个长度不超过 $2\cdot 10^5$ 的字符串 $t$，仅由字符 a-z 组成。请计算 $A(t)$，以及在经过 $U$ ($1\le U\le 2\cdot 10^5$) 次更新后 $A(t)$ 的变化情况，每次更新都会改变 $t$ 中的一个字符。更新是累积的。

输入格式

第一行输入字符串 $t$。

下一行输入 $U$，随后有 $U$ 行，每行包含一个位置 $p$ ($1\le p\le N$) 和一个字符 $c$（范围为 a-z），表示将 $t$ 的第 $p$ 个字符修改为 $c$。

输出格式

输出 $U+1$ 行，分别表示在没有任何更新之前以及每次更新之后，所有子串中能够构成的 "bessie" 总数。

样例

输入格式 1

bessiebessie
3
3 l
7 s
3 s

输出格式 1

14
7
1
7

说明

在没有任何更新之前，有 12 个子串恰好包含 1 个 "bessie"，有 1 个子串恰好包含 2 个 "bessie"，因此 "bessie" 的总数为 $12\cdot 1 + 1 \cdot 2 = 14$。

第一次更新后，$t$ 变为 "belsiebessie"。有 7 个子串恰好包含 1 个 "bessie"。

第二次更新后，$t$ 变为 "belsiesessie"。只有整个字符串包含 "bessie"。