Cow Pareidolia Subsequence Summation

Pareidolia is the phenomenon where you see recognizable patterns in unstructured images, for example, spotting a cow in everyday objects. Farmer John, being always around cows, often sees the pattern "bessie" in strings. More formally, for a string s, let B(s) denote the maximum number of repeated copies of bessie that can be obtained as a subsequence by deleting zero or more characters from s. For example, for s = bqessiyexbesszieb, we have B(s) = 2 because by ignoring some letters, one can get bessiebessie.

Given a string t consisting only of lowercase letters (a–z) and of length at most \(2\times10^5\), define A(t) as the sum of B(s) over all contiguous substrings s of t. Furthermore, there will be U updates (with \(1 \le U \le 2\times10^5\)). Each update changes one character of t (updates are cumulative). Your task is to compute A(t) for the initial string and then after each update.

Note: The pattern to search for is bessie. To form repeated copies, the subsequences must appear in order and non‐overlapping. All formulas in this statement are in LaTeX format. For example, the pattern occurs if and only if the string s has a subsequence that equals \(\texttt{bessie}\), and B(s) represents the maximum number of disjoint subsequences equal to \(\texttt{bessie}\) in s.

inputFormat

The input begins with a string t on its own line. This string consists only of lowercase letters (a–z).

The next line contains an integer U, the number of updates.

Each of the next U lines contains an update in the format:

pos c

Here, pos is a 1-indexed position in the string, and c is the new character to be placed at that position. Updates are cumulative.

Note: Although the original constraints allow string lengths and number of updates up to \(2\times10^5\), the sample test cases presented here will have small sizes. Your solution must be efficient enough to handle large inputs under the full constraints.

outputFormat

Output U+1 lines. The first line should contain A(t) for the initial string. Each of the next U lines should contain the new value of A(t) after applying the corresponding update.

Reminder: A(t) is the sum of B(s) over all contiguous substrings s of t, where B(s) is the maximum number of copies of bessie that can be obtained as a subsequence of s.

sample

bessie
0

1