Problems
Суффиксное дерево на очереди
Суффиксное дерево на очереди
Дана строка s, изначально она пустая. Также задана последовательность операций. Каждая операция одного из двух следующих типов:
добавить символ в конец строки s, длина строки увеличивается на 1;
удалить первый символ строки s, длина строки уменьшается на 1.
После каждой операции Вам нужно вывести количество различных подстрок в строке s на данный момент.
Input data
В первой строке записано целое число q (1 ≤ q ≤ 10^4) — количество операций. В следующих q строках записаны сами операции. Операция первого типа задана в формате "+ c", где c — маленькая буква латинского алфавита. Операция второго типа задана в формате "-".
Output data
Выведите q строк, для каждой операции количество различных подстрок в строке s после ее выполнения.
Examples
Input example #1
8 + a + a + b - + b - + c + a
Output example #1
1 2 5 3 5 2 5 9