% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$0.8$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача OS01. BESSIE}
\addauthor{Автор: Иван Лупов (заета)}{2026}{08}{29}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	8 – 10 клас
}

Ще дефинираме \texttt{bessie}-оценката на един низ $t$, като максималния брой срещания на подниза \texttt{bessie} в низа $t$, ако е позволено да изтриете някои от буквите на $t$. Например \texttt{bessie}-оценката на низа \texttt{bqessiyexbesszieb} е $2$. Допълнително дефинираме функцията $f(t)$, която приема низ $t$ и връща \texttt{bessie}-оценката на всеки подниз $t[l \dots r]$ за $1 \le l \le r \le |t|$.

Напишете програма \texttt{\textbf{bessie}}, която намира стойността на $f(t)$ за въведен низ $t$ и я преизчислява всеки път след $q$ на брой замени на букви в низа. Замените се натрупват.

\subsection{Вход}
От първия ред на стандартния вход се въвежда $t$ -- низ от малки латински букви. От втория ред се въвежда единствено числото $q$, което показва броя замени на букви от низа, които ще изпълним.

От всеки от следващите $q$ реда се въвежда по една двойка $x \ \alpha$, задаваща, че на позиция $x$ се записва буква $\alpha$.

\subsection{Изход}
На стандартния изход изведете $q + 1$ числа, всяко на отделен ред. Първото число е стойността на $f(t)$ за въведения низ и $i$-тото от следващите $q$ числа е стойността след $i$-тата замяна.

\subsection{Ограничения}
\begin{itemize}
	\item $1\le |t| \le 2 \times 10^5$
	\item $1 \le q \le 2 \times 10^5$
	\item $1 \le x \le 2 \times 10 ^ 5$ и $\alpha \in \{a, b, \dots, z\}$ за всяка заявка
	\item В $5\%$ от тестовете: $|t|, q \le 300$.
	\item В $15\%$ от тестовете: $q \le 10$.
	\item В $40\%$ от тестовете: $|t|, q \le 10^5$.
\end{itemize}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход}\\
		\hline
		\texttt{\makecell[lt]{bessiebessie\\3\\3 l\\7 s\\3 s}} & \texttt{\makecell[lt]{14\\7\\1\\7}}\\
		\hline
	\end{tblr}
\end{table}

\subsection{Обяснение}
След първата замяна низа става \texttt{belsiebessie}. След втората замяна низа става \texttt{belsiesessie}. Накрая низа е \texttt{bessiesessie}.

\end{document}
