이진 문자열

길이가 $n$인 문자열 $s_1 s_2 \ldots s_n$이 주어진다. 각 문자는 0, 1, ? 중 하나이다.

모든 $k \in [1, n]$에 대해 문자열 $T_k = t_1 t_2 \ldots t_n$을 다음과 같이 정의한다. 각 $1 \le i \le n$에 대해 다음을 따른다.

• $s_i \ne$ ?이면 $t_i = s_i$이다.
• 그렇지 않고 $i \le k$이면 $t_i =$ 0이다.
• 그 외에는 $t_i = t_{i-k}$이다. $t_{i-k}$를 재귀적으로 계산해서 $t_i$를 구할 수 있다.

$T_k$의 문자 집합은 01이다. 모든 $k \in [1, n]$에 대해 $T_k$에 있는 1의 개수를 구하라.

첫째 줄에 문자열의 길이 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에 길이 $n$의 문자열 $s_1 s_2 \ldots s_n$이 주어진다. 각 문자는 0, 1, ? 중 하나이다.

$n$개의 줄을 출력한다. $k$번째 줄에는 $T_k$에 있는 1의 개수를 출력한다.