如果字符 0 在此字符串中出现的次数不超过 $$$k$$$,或者字符 1 在此字符串中出现的次数不超过 $$$k$$$(或两者兼而有之),那么我们称由字符 0 和/或 1 组成的字符串 $$$t$$$ 为漂亮。例如,如果 $$$k = 3$$$,则字符串 101010, 111, 0, 00000, 1111111000 很漂亮,而字符串 1111110000, 01010101 则不漂亮。
给你一个字符串 $$$s$$$。你必须将它分成尽可能少的漂亮字符串,即。即,找到一个字符串序列 $$$t_1, t_2, \dots, t_m$$$,使得每个 $$$t_i$$$ 都很漂亮,$$$t_1 + t_2 + \dots + t_m = s$$$ (其中 $$$+$$$ 是连接运算符),并且 $$$m$$$ 是最小可能的。
对于从 $$$1$$$ 到 $$$|s|$$$ 的每个 $$$k$$$,找到可以将 $$$s$$$ 划分为这些字符串的最小可能数量(即分区中可能的最小 $$$m$$$)。
输入
唯一一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$)。 $$$s$$$ 的每个字符不是 0 就是 1。
输出
打印 $$$|s|$$$ 整数。当 $$$k = i$$$ 时,第 $$$i$$$ 个整数应等于 $$$s$$$ 分区中的最小字符串数。
示例
输入 #1
00100010
输出 #1
2 1 1 1 1 1 1 1
输入 #2
1001011100
输出 #2
3 2 2 2 1 1 1 1 1 1