Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Controversial Rounds

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice and Bob play a game. The game consists of several sets, and each set consists of several rounds. Each round is won either by Alice or by Bob, and the set ends when one of the players has won $$$x$$$ rounds in a row. For example, if Bob won five rounds in a row and $$$x = 2$$$, then two sets ends.

You know that Alice and Bob have already played $$$n$$$ rounds, and you know the results of some rounds. For each $$$x$$$ from $$$1$$$ to $$$n$$$, calculate the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$x$$$ rounds in a row. It is possible that the last set is still not finished — in that case, you should not count it in the answer.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of rounds.

The second line contains one string $$$s$$$ of length $$$n$$$ — the descriptions of rounds. If the $$$i$$$-th element of the string is 0, then Alice won the $$$i$$$-th round; if it is 1, then Bob won the $$$i$$$-th round, and if it is ?, then you don't know who won the $$$i$$$-th round.

Output

In the only line print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$i$$$ rounds in a row.

Examples

Input

6 11?000

Output

6 3 2 1 0 0

Input

5 01?01

Output

5 1 0 0 0

Input

12 ???1??????1?

Output

12 6 4 3 2 2 1 1 1 1 1 1

Note

Let's consider the first test case:

- if $$$x = 1$$$ and $$$s = 110000$$$ or $$$s = 111000$$$ then there are six finished sets;
- if $$$x = 2$$$ and $$$s = 110000$$$ then there are three finished sets;
- if $$$x = 3$$$ and $$$s = 111000$$$ then there are two finished sets;
- if $$$x = 4$$$ and $$$s = 110000$$$ then there is one finished set;
- if $$$x = 5$$$ then there are no finished sets;
- if $$$x = 6$$$ then there are no finished sets.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 03:33:03 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|