Suffix tree in line

Given an initially empty string (s), you are provided with a sequence of operations. Each operation is one of the following two types:

1. Add a character to the end of the string (s), which increases the length of the string by (1).

2. Remove the first character from the string (s), which decreases the length of the string by (1).

After performing each operation, you must output the number of distinct substrings present in the string (s) at that moment.

Input

The first line contains an integer (q) ((1 $\le$ q $\le$ 10^4)) — the number of operations. The following (q) lines describe the operations. An operation of the first type is represented as "(+ c)", where (c) is a lowercase letter from the Latin alphabet. An operation of the second type is represented as "(-)".

Output

Output (q) lines, each containing the number of distinct substrings in the string (s) after executing the corresponding operation.

Examples