QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB
[-5]
Statistics

题目描述

给定一个长度为 n、字符集为 01? 的字符串 s1s2sn

对于任意 k[1,n],考察字符串 Tk=t1t2tn,其中对于 1in

  • si ?,则 ti=si
  • 否则,若 ikti= 0
  • 否则 ti=tik,你可以通过递归地算出 tik 得到 ti

容易发现 Tk 的字符集为 01。你需要对所有 k[1,n] 求出 Tk1 的个数。

输入格式

从标准输入读入数据。

输入的第一行一个整数 n(1n105) 表示字符串长度,第二行一个长度为 n、字符集为 01? 的字符串 s1s2sn

输出格式

输出到标准输出。

输出 n 行,第 i 行一个整数表示 Ti1 的个数。

样例

输入

5
10?1?

输出

3
4
2
3
2

解释

T1= 10011T2= 10111T3= 10010T4= 10011T5= 10010