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