Alice 和 Bob 玩游戏。比赛由几局组成,每局又由几轮组成。每轮由 Alice 或 Bob 获胜,当其中一名玩家连续赢得 $$$x$$$ 轮时,该组结束。例如,如果鲍勃连续赢得五轮且 $$$x = 2$$$,则两盘结束。
您知道 Alice 和 Bob 已经玩了 $$$n$$$ 轮,并且您知道某些轮的结果。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$x$$$,如果每组持续到其中一名玩家连续赢得 $$$x$$$ 轮,则计算可能已经完成的最大可能组数。最后一组可能还没有完成——在这种情况下,你不应该把它算在答案中。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 轮数。
第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$ — 回合的描述。如果字符串的第 $$$i$$$ 个元素为 0,则 Alice 赢得第 $$$i$$$ 轮;如果是 1,那么 Bob 赢得了第 $$$i$$$ 轮,如果是 ?,那么你不知道谁赢得了第 $$$i$$$ 轮。
输出
在唯一的行中打印 $$$n$$$ 整数。如果每组持续到其中一名玩家连续赢得 $$$i$$$ 轮,则第 $$$i$$$ 个整数应等于可能已经完成的最大可能组数。
示例
输入 #1
6 11?000
输出 #1
6 3 2 1 0 0
输入 #2
5 01?01
输出 #2
5 1 0 0 0
输入 #3
12 ???1??????1?
输出 #3
12 6 4 3 2 2 1 1 1 1 1 1
注意
让我们考虑第一个测试用例:
- 如果 $$$x = 1$$$ 且 $$$s = 110000$$$ 或 $$$s = 111000$$$ 则有六组成品;
- 如果 $$$x = 2$$$ 且 $$$s = 110000$$$ 则有三组成品;
- 如果 $$$x = 3$$$ 且 $$$s = 111000$$$ 则有两套成品;
- 如果 $$$x = 4$$$ 并且 $$$s = 110000$$$ 则有一套完成的;
- 如果 $$$x = 5$$$ 则没有完成的集合;
- 如果 $$$x = 6$$$ 则没有完成的集合。