Khoảng cách giữa các bit một

Cho xâu nhị phân $s$ dài $n$ , đánh chỉ số từ $0$ . Với mỗi khoảng cách $k = 1, \dots, n - 1$ , đếm số chỉ số $i$ thỏa $0 \leq i < n - k$ và cả $s_{i}, s_{i + k}$ đều bằng $1$ . In các đáp án theo $k$ tăng dần.

Input

Một dòng chứa xâu nhị phân $s$ .

Output

In $n - 1$ số; số thứ $k$ là đáp án cho khoảng cách $k$ .

Constraints

$2 \leq ∣ s ∣ \leq 2 \cdot 1 0^{5}$ ; $s$ chỉ gồm $0$ và $1$ .

Scoring

Subtask $1$ ( $50$ điểm): Kích thước dữ liệu và số lượng token đủ nhỏ để có thể kiểm tra trực tiếp.
Subtask $2$ ( $50$ điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input

Output

0 1

Giải thích: Với mỗi khoảng cách, ta duyệt các cặp vị trí cách nhau đúng khoảng đó và chỉ giữ những cặp đều là bit $1$ .

Lời giải tóm tắt

Thuật toán: Đặt A[i]=1 nếu s[i]='1', ngược lại 0. Đặt B[n-1-i]=A[i]. Tính C=A*B. Với khoảng cách k, hệ số C[n-1-k] bằng
Thuật toán: sum_i A[i] A[i+k].
Thuật toán: In hệ số đó cho mọi k.
Chứng minh đúng: Thay định nghĩa của B vào C[n-1-k]: phần tử ghép với A[i] là B[n-1-k-i]=A[i+k]. Chỉ cặp 1,1 đóng góp 1, do đó tổng chính là số cặp cách nhau k.
Độ phức tạp: O(n log n) thời gian, O(n) bộ nhớ.