Un borde de una cadena es un prefijo que también es un sufijo de la cadena, pero no de la cadena completa. Por ejemplo, los bordes de ~abcababcab~ son ~ab~ y ~abcab~.

Su tarea es encontrar todas las longitudes de los bordes de una cadena dada.

Entrada

La única línea de entrada contiene una cadena de longitud ~n~ que consta de caracteres de la ~a~ a la ~z~.

Salida

Imprima todas las longitudes de los bordes de la cadena en orden creciente.

Restricciones

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

Ejemplo de Entrada

abcababcab

Ejemplo de Salida

2 5