Given a string $s_1s_2 \cdots s_n$ of length $n$ consisting of characters from the set $\{`0`, `1`, `?`\}$.

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$, $t_i =$ 0;
• Otherwise, $t_i = t_{i-k}$, which can be determined by recursively calculating $t_{i-k}$.

It is easy to see that the character set of $T_k$ is $\{`0`, `1`\}$. You need to find the number of 1s in $T_k$ for all $k \in [1, n]$.

Input

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_1s_2\cdots s_n$ of length $n$ consisting of characters from $\{`0`, `1`, `?`\}$.

Output

Output $n$ lines, where the $i$-th line contains an integer representing the number of 1s in $T_i$.

Examples

Input 1

5
10?1?

Output 1

3
4
2
3
2

Note

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