Binary String

You are given a string $s_1 s_2 \ldots s_n$ of length $n$ with elements from the character set "01?".

For every $k \in [1, n]$, consider the string $T_k = t_1 t_2 \ldots t_n$ where, for $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}$, and you can recursively compute $t_{i-k}$ to obtain $t_i$.

It is easy to see that the character set of $T_k$ is "01". You need to calculate the number of 1 in $T_k$ for all $k \in [1, n]$.

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

The second line contains the string $s_1 s_2 \ldots s_n$ of length $n$ with elements from the character set "01?".

Output $n$ lines, where the $k$-th line contains an integer representing the number of 1 in $T_k$.