Suffix tree in line#5914
Given an initially empty string , you are given a sequence of operations. Each operation is one of the following two types:
Add a character to the end of the string , increasing the length of by .
Remove the first character from the string , decreasing the length of by .
After each operation, output the number of distinct substrings present in the string at that moment.
The first line contains an integer (1 \leq q \leq 10^4) — the number of operations. The next lines describe the operations. A type 1 operation is given as "+ c", where is a lowercase letter of the Latin alphabet. A type 2 operation is given as "-".
Print lines, each containing the number of distinct substrings in the string after performing the corresponding operation.
Example 1