Задано рядок \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} після її виконання.