By Gabriel Dalalio, ITA Brazil
Initially, there is an empty string. Your program should perform two types of instructions:
For example, the string "aba" has 5 different substrings: "a", "ab", "aba", "b", "ba".
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.
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|