题目背景

翻译自 CSES-2115 题。

题目描述

给定一个长度为 $n$ 的二进制字符串。你的任务是计算对于每个 $k$（$0 \le k \le n$），包含恰好 $k$ 个 $1$ 的非空子串的数量。

例如，如果字符串是 $101$，结果如下：

• $1$ 个子串包含 $0$ 个 $1$：$0$
• $4$ 个子串包含 $1$ 个 $1$：$01, 1, 1, 10$
• $1$ 个子串包含 $2$ 个 $1$：$101$
• $0$ 个子串包含 $3$ 个 $1$

输入格式

唯一的输入行是一个长度为 $n$ 的二进制字符串。

输出格式

输出 $n + 1$ 个值，表示每个 $k$（从 $0$ 到 $n$）包含恰好 $k$ 个 $1$ 的子串的数量。

样例

101

1 4 1 0

数据范围

• $1 \le n \le 2 \times 10^5$