May I Add a Letter?

You have a string S of length $N$, and you must perform a sequence of $Q$ updates of two types on S:

• Append a given character to the end of S.
• Delete the last character from S.

Initially, and after each update, you must calculate the number of distinct strings that occur at least twice as substrings of S.

For example, if S is initially ABABC, the answer is 3, because A, B, and AB each occur twice as substrings of S. If you append the character C, S becomes ABABCC and the answer is 4, because C now occurs twice too. If you append C again, S becomes ABABCCC and the answer is 5, because CC now occurs twice. If you then perform a delete operation, S becomes ABABCC and the answer is 4 again.

The first line contains the string S of length $N$, the initial value of S. Each character of S is an uppercase letter.

The second line contains the string U of length $Q$, the updates to perform. Each character of U is either an uppercase letter, which means that letter must be appended, or the character - (hyphen), which denotes a delete operation. The updates must be applied in the order they appear in U. It is guaranteed that delete operations are never applied to an empty string.

Constraints: $1 \le N \le 10^5$, $1 \le Q \le 10^5$.

Output $Q + 1$ lines. Line 1 gives the answer for the initial value of S. Line $i + 1$ gives the answer after applying the first $i$ updates ($i = 1, 2, \ldots, Q$).