Задачі
Суфіксне дерево на черзі
Суфіксне дерево на черзі
Задано рядок \textbf{s}, спочатку він порожній. Також задано послідовність операцій. Кожна операція одного з двох наступних типів:
\begin{enumerate}
\item додати символ у кінець рядкаи \textbf{s}, довжина рядка збільшкється на \textbf{1};
\item видалити перший символ рядка \textbf{s}, довжина рядка зменшується на \textbf{1}.
\end{enumerate}
Після кожної операції Вам потрібно вивести кількість різних підрядків у рядку \textbf{s} на даний момент.
\InputFile
У першому рядку записано ціле число \textbf{q} (\textbf{1} ≤ \textbf{q} ≤ \textbf{10^4}) --- кількість операцій. У наступних \textbf{q} рядках записані самі операції. Операція першого типу задана у форматі "\textbf{+ c}", де \textbf{c} --- маленька буква латинського алфавіту. Операція другого типу задана у форматі "\textbf{-}".
\OutputFile
Виведіть \textbf{q} рядків, для кожної операції кількість різни підрядків у рядку \textbf{s} після її виконання.
Вхідні дані #1
8 + a + a + b - + b - + c + a
Вихідні дані #1
1 2 5 3 5 2 5 9