33417번 - 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$.

제한

힌트