Cho một xâu nhị phân có độ dài \(n\). Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\) đếm số cách chọn \(i\) và \(j\) sao cho \(i - j = k\) và cả hai vị trí đều chứa bit \(1\).

Input

• Một dòng duy nhất chứa một xâu chỉ bao gồm kí tự 0 và 1
• \(2 \leq n \leq 2\cdot 10^5\) với \(n\) là độ dài xâu

Output

• Với mỗi \(k\) trong khoảng \(1 \ldots n - 1\), in ra số cách có thể chọn được hai vị trí như vậy.

Example

1001011010

1 2 3 0 2 1 0 1 0