URI Online Judge | 1530

How Many Substrings?

By Gabriel Dalalio, ITA BR Brazil

Timelimit: 2

Initially, there is an empty string. Your program should perform two types of instructions:

  1. Add a character between 'a' and 'z' at the end of the string.
  2. Calculate how many different substrings can be found in the string.

For example, the string "aba" has 5 different substrings: "a", "ab", "aba", "b", "ba".

Input

The input consists of several test cases. Each test case consists of a line containing a sequence of up to 2.105 characters. Each character represents an instruction that must be taken. A character between 'a' and 'z' indicates that an instruction of type 1 must be performed with this character. A character '?' represents an instruction of type 2.

Output

For each instruction of type 2, print a line containing the number of different substrings that can be found in the string.

Sample Input Sample Output

aba?
?z?z?z?
abc?abc?

5
0
1
2
3
6
15