Un período de una cadena es un prefijo que se puede usar para generar toda la cadena repitiendo el prefijo. La última repetición puede ser parcial. Por ejemplo, los períodos de ~ABCABCA~ son ~ABC, ABCABC~ y ~ABCABCA~.

Su tarea es encontrar todas las longitudes de período de una cadena.

Entrada

La única línea de entrada tiene una cadena de longitud ~n~ que consiste en caracteres ~A-Z~.

Salida

Imprima todas las longitudes de período en orden creciente.

Restricciones

• ~1 \leq n \leq 10^6~

Ejemplo de Entrada

abcabca

Ejemplo de Salida

 3 6 7