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

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

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

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

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

Входные данные

В первой строке записано целое число q (1 ≤ q ≤ 10^4) — количество операций. В следующих q строках записаны сами операции. Операция первого типа задана в формате "+ c", где c — маленькая буква латинского алфавита. Операция второго типа задана в формате "-".

Выходные данные

Выведите q строк, для каждой операции количество различных подстрок в строке s после ее выполнения.

Примеры