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