**Примечание. Ограничение по времени для этой задачи составляет 4 секунды, что в два раза больше, чем по умолчанию.
Ограничение по памяти для этой задачи составляет 512 МБ, вдвое больше, чем по умолчанию.**
Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры,
которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон
постоянно находится рядом с коровами, он часто видит
коровьи узоры в повседневных предметах. Например, если он смотрит на
строка "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и
все, что он видит, это «bessiebessie».
Дана строка \(s\), пусть \(B(s)\) представляет собой максимальное количество повторяющихся копий.
из «bessie» можно получить, удалив ноль или более символов из \(s\).
В приведенном выше примере \(B(\)"bqessiyexbesszieb"\() = 2\). Кроме того, учитывая
строка \(t\), пусть \(A(t)\) представляет собой сумму \(B(s)\) по всем непрерывным
подстроки \(s\) строки \(t\).
У фермера Джона есть строка \(t\) длины не более \(2\cdot 10^5\), состоящая только из
символов a-z. Пожалуйста, рассчитайте \(A(t)\) и как \(A(t)\) изменится после \(U\)
(\(1\le U\le 2\cdot 10^5\)) обновлений, каждое из которых изменяет символ \(t\). Обновления
являются кумулятивными.
ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):
Первая строка ввода содержит
\(t\).
Следующая строка содержит \(U\), за которыми следуют строки по \(U\), каждая из которых содержит позицию \(p\)
(\(1\le p\le N\)) и символ \(c\) в диапазоне от a до z, что означает, что \(p\)-й
символ \(t\) заменяется на \(c\).
ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):
Выведите \(U+1\) строк — общее количество «bessie», которое можно сделать во всех
подстроках \(t\) перед любыми обновлениями и после каждого обновления.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
bessiebessie
3
3 l
7 s
3 s
|
14
7
1
7
|