Se le proporciona una cadena de bits de longitud ~n~. Su tarea consiste en calcular, para cada ~k~ entre ~0 \ldots n~, el número de subcadenas no vacías que contienen exactamente ~k~ unos.

Por ejemplo, si la cadena es ~101~, hay:

• 1 subcadena que contiene 0 unos: 0.
• 4 subcadenas que contienen 1 uno: 01, 1, 1, 10.
• 1 subcadena que contiene 2 unos: 101.
• 0 subcadenas que contienen 3 unos.

Entrada

La única línea de entrada contiene una cadena binaria de longitud ~n~.

Salida

Imprima ~n+1~ valores como se especificó anteriormente.

Restricciones

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

Ejemplo de Entrada

101

Ejemplo de Salida

1 4 1 0