파레이돌리아

파레이돌리아는 실제로는 없는 장면에서 눈이 익숙한 무늬를 보게 되는 현상이다. 예를 들어 구름에서 얼굴을 보는 것이 그렇다. 농부 존은 늘 소 곁에 있어서, 일상의 물건에서도 소와 관련된 무늬를 자주 본다. 예를 들어 문자열 "bqessiyexbesszieb"를 보면, 일부 글자를 무시하고 "bessiebessie"만 보게 된다.

문자열 $s$가 주어졌을 때, $B(s)$는 $s$에서 0개 이상의 문자를 지워 만들 수 있는 "bessie"의 최대 반복 횟수이다. 위 예에서 $B("bqessiyexbesszieb") = 2$이다. 문자열 $t$가 주어졌을 때, $A(t)$는 $t$의 모든 연속 부분 문자열 $s$에 대한 $B(s)$의 합이다.

농부 존에게는 길이가 최대 $2\cdot 10^5$이고 a-z 소문자로만 이루어진 문자열 $t$가 있다. $A(t)$를 구하고, $t$의 문자 하나를 바꾸는 갱신을 $U$번($1\le U\le 2\cdot 10^5$) 했을 때 $A(t)$가 어떻게 바뀌는지 구하라. 갱신은 누적된다.

첫 줄에 문자열 $t$가 주어진다. 다음 줄에 $U$가 주어지고, 이어서 $U$개의 줄에 각각 위치 $p$ ($1\le p\le N$)와 a-z 범위의 문자 $c$가 주어진다. 이는 $t$의 $p$번째 문자를 $c$로 바꾼다는 뜻이다.

갱신 전과 매 갱신 후에, $t$의 모든 부분 문자열로 만들 수 있는 "bessie"의 총 개수를 $U+1$줄에 출력한다.

갱신 전에는 정확히 1개의 "bessie"를 포함하는 부분 문자열이 12개이고, 정확히 2개를 포함하는 문자열이 1개이므로 총 개수는 $12\cdot 1 + 1 \cdot 2 = 14$이다. 갱신을 한 번 하면 $t$는 "belsiebessie."가 되고, 정확히 하나의 "bessie"를 포함하는 부분 문자열은 7개이다. 갱신을 두 번 하면 $t$는 "belsiesessie."가 되고, "bessie"를 포함하는 것은 전체 문자열뿐이다.