Binary String

You are given a string $s_1 s_2 \ldots s_n$ of length $n$. Each character is one of 0, 1, or ?.

For every $k \in [1, n]$, define the string $T_k = t_1 t_2 \ldots t_n$ as follows. For each $1 \le i \le n$:

• If $s_i \ne$ ?, then $t_i = s_i$.
• Otherwise, if $i \le k$, then $t_i =$ 0.
• Otherwise, $t_i = t_{i-k}$. You can compute $t_{i-k}$ recursively to obtain $t_i$.

The character set of $T_k$ is 01. For every $k \in [1, n]$, count the number of 1 characters in $T_k$.

The first line contains an integer $n$ ($1 \le n \le 10^5$), the length of the string.

The second line contains the string $s_1 s_2 \ldots s_n$ of length $n$. Each character is one of 0, 1, or ?.

Print $n$ lines. The $k$-th line contains the number of 1 characters in $T_k$.