eolymp
bolt
Try our new interface for solving problems
Problems

Суффиксное дерево на очереди

Суффиксное дерево на очереди

Time limit 1 second
Memory limit 256 MiB

Дана строка s, изначально она пустая. Также задана последовательность операций. Каждая операция одного из двух следующих типов:

  1. добавить символ в конец строки s, длина строки увеличивается на 1;

  2. удалить первый символ строки s, длина строки уменьшается на 1.

После каждой операции Вам нужно вывести количество различных подстрок в строке s на данный момент.

Input data

В первой строке записано целое число q (1q10^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
Author Геральд Агапов
Source Летняя школа Севастополь 2013, Волна 1, День 6