题目描述
给定一个长度为 n、字符集为 01?
的字符串 s1s2⋯sn。
对于任意 k∈[1,n],考察字符串 Tk=t1t2⋯tn,其中对于 1≤i≤n,
- 若 si≠
?
,则 ti=si; - 否则,若 i≤k,ti=
0
; - 否则 ti=ti−k,你可以通过递归地算出 ti−k 得到 ti。
容易发现 Tk 的字符集为 01
。你需要对所有 k∈[1,n] 求出 Tk 中 1
的个数。
输入格式
从标准输入读入数据。
输入的第一行一个整数 n(1≤n≤105) 表示字符串长度,第二行一个长度为 n、字符集为 01?
的字符串 s1s2⋯sn。
输出格式
输出到标准输出。
输出 n 行,第 i 行一个整数表示 Ti 中 1
的个数。
样例
输入
5
10?1?
输出
3
4
2
3
2
解释
T1= 10011
,T2= 10111
,T3= 10010
,T4= 10011
,T5= 10010
。