Se te proporciona una cadena binaria de longitud ~n~. Tu tarea consiste en calcular, para cada ~k~ entre ~1 \ldots n-1~, el número de maneras en que podemos elegir dos posiciones ~i~ y ~j~ tales que ~i-j=k~ y que ambas posiciones tengan un bit a uno.

Entrada

La única línea de entrada contiene una cadena formada únicamente por los caracteres ~0~ y ~1~.

Salida

Para cada distancia ~k~ entre ~1 \ldots n-1~, imprime el número de maneras en que podemos elegir dos de tales posiciones.

Restricciones

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

Ejemplo de Entrada

1001011010

Ejemplo de Salida

1 2 3 0 2 1 0 1 0