Counting Ones in Recursively Defined Binary Strings

You are given a string \(s = s_1s_2\cdots s_n\) of length \(n\) whose characters belong to the set \(\{0, 1, ?\}\). For each \(k \in [1, n]\), define a new string \(T_k = t_1 t_2 \cdots t_n\) according to the following rules for every index \(i\) (1-indexed):

• If \(s_i \neq \texttt{'?'}\), then \(t_i = s_i\).
• If \(s_i = \texttt{'?'}\) and \(i \le k\), then \(t_i = \texttt{'0'}\).
• If \(s_i = \texttt{'?'}\) and \(i > k\), then \(t_i = t_{i-k}\). (Note that you can obtain \(t_i\) recursively.)

It is easy to verify that for every \(k\), the string \(T_k\) contains only the characters \(0\) and \(1\). Your task is to compute, for every \(k \in [1,n]\), the number of occurrences of \(1\) in \(T_k\).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le \text{some upper limit})\) representing the length of the string.

The second line contains a string \(s\) of length \(n\), consisting of characters from the set \(\{0,1,?\}\).

outputFormat

Output a single line containing \(n\) integers separated by a space. The \(k\)-th integer should be the number of \(1\)'s in the string \(T_k\) defined above.

sample

3
1?0

2 2 1