Pareidolia to zjawisko polegające na tym, że oczy mają tendencję do dostrzegania znajomych wzorów na obrazach, na których naprawdę ich nie ma, na przykład twarzy w chmurze. Jak można sobie wyobrazić, ponieważ Farmer John nieustannie przebywa blisko krów, często widzi wzory związane z krowami w codziennych przedmiotach. Na przykład, kiedy patrzy na napis "bqessiyexbesszieb", jego oczy pomijają niektóre litery i widzi jedynie "bessiebessie".
Dla napisu $s$ niech $B(s)$ oznacza maksymalną liczbę powtarzających się kopii "bessie", które można utworzyć przez usunięcie z $s$ zera lub większej liczby znaków. W powyższym przykładzie $B(\texttt{bqessiyexbesszieb}) = 2$.
Obliczenie $B(s)$ jest ciekawym wyzwaniem, ale Farmer John chce rozwiązać jeszcze ciekawsze: dla napisu $t$ długości co najwyżej $3\cdot 10^5$, złożonego wyłącznie ze znaków a-z, oblicz sumę $B(s)$ po wszystkich spójnych podnapisach $s$ napisu $t$.
Wejście
Wejście zawiera niepusty napis długości co najwyżej $3\cdot 10^5$, którego wszystkie znaki są małymi literami alfabetu angielskiego.
Wyjście
Wypisz jedną liczbę: łączną liczbę kopii "bessie", które można utworzyć we wszystkich podnapisach napisu wejściowego.
Przykład
Wejście 1
bessiebessie
Wyjście 1
14
Uwagi
Dwanaście podnapisów zawiera dokładnie 1 "bessie", a 1 napis zawiera dokładnie 2 kopie "bessie", więc suma wynosi $12\cdot 1 + 1 \cdot 2 = 14$.
Wejście 2
abcdefghssijebessie
Wyjście 2
28
Podzadania
- Dane wejściowe 3-5: długość napisu wynosi co najwyżej $5000$.
- Dane wejściowe 6-12: brak dodatkowych ograniczeń.
Autorzy zadania: Brandon Wang i Benjamin Qi