Void exists in the world. There are two types of void, denoted here as $0$ and $1$.

Stars are born from the void. A regular arrangement of the void is called a star, which is a $01$ sequence.

The void possesses a will. A star is mutable; it can be partitioned into $m$ parts, where each part is a contiguous segment of the original star.

The world follows the second law of thermodynamics. The arrangement of the void always tends toward regularity. We use the length of the Longest Non-Decreasing Subsequence (LNDS) as a measure. After the $m$ segments of the star are rearranged, they will always reach a state that maximizes the length of the LNDS.

However, $m$ is not fixed. You need to find the maximum possible length of the LNDS as described above for every possible $m$.

Given a $01$ string $a_{1\cdots n}$ of length $n$, for each $m \in [1, n]$, calculate:

• The maximum length of the LNDS of a new sequence formed by partitioning $a_{1\cdots n}$ into $m$ segments and concatenating these segments in any order.

Input

The first line contains an integer $n$.

The second line contains a $01$ string of length $n$, where the $i$-th character represents $a_i$.

Output

Output $n$ integers on a single line, representing the answers for $m = 1, 2, \cdots, n$, respectively.

Examples

Input 1

8
01100100

Output 1

5 7 7 8 8 8 8 8

Note 1

• For $m=1$, the string is partitioned into $01100100$, and the LNDS is $\underline{0}11\underline{00}1\underline{00}$.
• For $m=2$, the string is partitioned into $011, 00100$, which can be concatenated as $00100011$, and the LNDS is $\underline{00}1\underline{00011}$.
• For $m=3$, the string is partitioned into $011, 001, 00$, which can be concatenated as $00001011$, and the LNDS is $\underline{00001}0\underline{11}$.
• For $m=4$, the string is partitioned into $011, 00, 1, 00$, which can be concatenated as $00000111$, and the LNDS is $\underline{00000111}$.
• For $m>4$, the result of the concatenation is the same as for $m=4$. Note that the partitions and concatenation schemes shown above, as well as the LNDS, may not be unique.

Input 2

20
10110001010110001101

Output 2

12 14 14 16 16 17 17 18 18 19 19 20 20 20 20 20 20 20 20 20

Subtasks

For all data: $1 \le n \le 3 \times 10^5$.

Subtask 1 (15 pts): $n \le 8$.

Subtask 2 (15 pts): $n \le 20$.

Subtask 3 (15 pts): $n \le 200$.

Subtask 4 (20 pts): $n \le 2\,000$.

Subtask 5 (20 pts): $n \le 80\,000$.

Subtask 6 (15 pts): No special restrictions.