Dada una cadena, calcule para cada posición la longitud del palíndromo más largo que termina en esa posición.

Entrada

La única línea contiene una cadena de longitud n. Cada carácter es uno de la ~a-z~.

Salida

Imprima ~n~ números: la longitud de cada palíndromo.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~

Ejemplo de Entrada

ababbababaa

Ejemplo de Salida

1 1 3 3 2 4 6 8 5 5 2