Pareidolia

문제

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiebessie".

Given a string $ss$, let $B(s)B(s)$ represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from $ss$. In the example above, $B(B($"bqessiyexbesszieb"$)=2)\; =\; 2$. Furthermore, given a string $tt$, let $A(t)A(t)$ represent the sum of $B(s)B(s)$ over all contiguous substrings $ss$ of $tt$.

Farmer John has a string $tt$ of length at most $2\cdot {10}^{5}2\backslash cdot\; 10^5$ consisting only of characters a-z. Please compute $A(t)A(t)$, and how $A(t)A(t)$ would change after $UU$ ($1\le U\le 2\cdot {10}^{5}1\backslash le\; U\backslash le\; 2\backslash cdot\; 10^5$) updates, each changing a character of $tt$. Updates are cumulative.

입력

The first line of input contains $tt$.

The next line contains $UU$, followed by $UU$ lines each containing a position $pp$ ($1\le p\le N1\backslash le\; p\backslash le\; N$) and a character $cc$ in the range a-z, meaning that the $pp$th character of $tt$ is changed to $cc$.

출력

Output $U+1U+1$ lines, the total number of bessies that can be made across all substrings of $tt$ before any updates and after each update.

힌트

Before any updates, twelve substrings contain exactly 1 "bessie" and 1 string contains exactly 2 "bessie"s, so the total number of bessies is $12\cdot 1+1\cdot 2=1412\backslash cdot\; 1\; +\; 1\; \backslash cdot\; 2\; =\; 14$.

After one update, $tt$ is "belsiebessie." Seven substrings contain exactly one "bessie."

After two updates, $tt$ is "belsiesessie." Only the entire string contains "bessie."

bessiebessie
3
3 l
7 s
3 s

14
7
1
7