Дана строка \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} после ее выполнения.