Easy Operations

给定一个长度为 $n$ 的 $01$ 串 $a$，对于每个 $0\le k\le n-1$ 解决如下问题：

• 选择 $a$ 中的一些元素翻转（$0\rightarrow 1,1\rightarrow 0$），使得 $\sum\limits_{i=1}^{n-1}[a_i\neq a_{i+1}]=k$。求翻转的元素个数的最小值。

输入格式

一行，一个 $01$ 串 $a$，$n$ 定义为 $a$ 的长度。

输出格式

一行，$n$ 个整数，第 $i$ 个整数表示 $k=i-1$ 时的答案。

提示

对于 $100\%$ 的数据，$n\le 5\times 10^5$。

$\text{Subtask }1(16\%):n\le 5000$。

$\text{Subtask }2(84\%):$ 无特殊限制。