Consideremos una cadena de ~n~ caracteres, indexada del ~1~ al ~n~. Su tarea consiste en calcular todos los valores de las siguientes funciones:

• ~z(i)~ representa la longitud máxima de una subcadena que comienza en la posición ~i~ y es un prefijo de la cadena. Además, ~z(1) = 0~.
• ~\pi(i)~ representa la longitud máxima de una subcadena que termina en la posición ~i~, es un prefijo de la cadena y cuya longitud es como máximo ~i-1~.

Tenga en cuenta que la función ~z~ se utiliza en el algoritmo ~Z~, y la función ~\pi(i)~ en el algoritmo KMP.

Entrada

La única línea de entrada contiene una cadena de longitud ~n~. Cada carácter está entre la a y la z.

Salida

Imprima dos líneas: primero los valores de la función ~z~ y luego los valores de la función ~\pi(i)~.

Restricciones

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

Ejemplo de Entrada

abaabca

Ejemplo de Salida

0 0 1 2 0 0 1
0 0 1 1 2 0 1