Problem Description

Given a string $s_1 s_2 \cdots s_n$ of length $n$ over the alphabet 01?.

For any $k \in [1,n]$, consider the string $T_k = t_1 t_2 \cdots 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}$. You can compute $t_i$ by recursively finding $t_{i-k}$.

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

Input Format

The first line contains an integer $n \ (1 \le n \le 10^5)$, representing the length of the string.
The second line contains a string $s_1 s_2 \cdots s_n$ of length $n$ over the alphabet 01?.

Output Format

Output $n$ lines. On the $i$-th line, output one integer representing the number of 1 in $T_i$.

5
10?1?

3
4
2
3
2

Hint

$T_1 =$ 10011, $T_2 =$ 10111, $T_3 =$ 10010, $T_4 =$ 10011, $T_5 =$ 10010.

Translated by ChatGPT 5