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

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

1. додати символ у кінець рядкаи s, довжина рядка збільшкється на 1;

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

Після кожної операції Вам потрібно вивести кількість різних підрядків у рядку s на даний момент.

Вхідні дані

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

Вихідні дані

Виведіть q рядків, для кожної операції кількість різни підрядків у рядку s після її виконання.

Приклади