bee 1530 - Quantas Substrings?

Iniciamente, há uma string vazia. Seu programa deve realizar dois tipos de instruções:

Adicionar um caractere entre 'a' e 'z' ao final da string.
Calcular quantas substrings diferentes a string possui.

Por exemplo, a string "aba" possui 5 substrings diferentes: "a", "ab", "aba", "b", "ba".

Entrada

A entrada é composta por vários casos de teste. Cada caso de teste consiste de uma linha contendo uma sequência com até 2.10⁵ caracteres. Cada caractere representa uma instrução que deve ser feita. Um caractere entre 'a' e 'z' indica que deve ser realizado uma instrução do tipo 1 com esse caractere. Um caractere '?' representa uma instrução do tipo 2.

Saída

Para cada instrução do tipo 2, imprima uma linha contendo o número de substrings diferentes que a string possui.

Exemplo de Entrada	Exemplo de Saída
aba? ?z?z?z? abc?abc?	5 0 1 2 3 6 15