Se le da una cadena de longitud ~n~ ~(1 \leq n \leq 2 \cdot 10^3)~. Para cada número entero entre ~1~ y ~n~, usted debe imprimir el número de subcadenas distintas de esa longitud.

Entrada

La única línea de entrada tiene una cadena de longitud ~n~ formada por los caracteres a-z.

Salida

Para cada entero entre ~1 \ldots n~ imprime el número de subcadenas distintas de esa longitud.

Ejemplo de Entrada

abab

Ejemplo de Salida

2 2 2 1

Explicacion de la Salida

Hay dos cadenas diferentes de largo ~1~, que son a y b; hay dos cadenas diferentes de largo ~2~, que son ab y ba; hay dos cadenas diferentes de largo ~3~, que son aba y bab; y una cadena largo ~4~, que es abab.