题目描述
新年就要到了,小 L 想要送给可爱的小 Y 一个美丽的花环。
一个花环可以由一个小写字母字符串 $s$ 所表示,$s_i$ 表示第 $i$ 朵花花的颜色。
现在小 L 有一个长度为 $n$ 的初始花环,他会从上面剪除恰好一段长度为 $k$ 的连续段,再把花环剩余的部分重新首尾相接,成为一个新的花环。
小 L 认为一个花环是美观的,当且仅当花环上每一对相邻的花花的颜色都是不同的。请注意,由于是一个环,花环上第一朵花花和最后一朵花花也是相邻的(长度为 $1$ 除外)。
现在对于每一个正整数 $k \in [0,n-1]$ ,请你告诉小 L 他能否得到一个美观的花环。
输入格式
第一行一个正整数 $n$ 表示花环的长度。
第二行一个小写字母字符串表示初始花环。
输出格式
一行一个长度为 $n$ 的 $01$ 串 $ans$。
其中第 $i$ 位表示当 $k=i-1$ 时的答案。$ans_i=1$ 表示此时可以得到美观的花环,否则 $ans_i=0$。
样例输入 1
5
qaqaq
样例输出 1
01011
【样例解释】
- $k=0$ 时,初始花环并不是美观的;
- $k=1$ 时,我们可以删除 $s[1,1]$ ,花环变为
aqaq
,是美观的; - $k=2$ 时,我们只能得到
aqa
或者qaq
均为不美观的; - $k=3$ 时,我们可以删除 $s[1,3]$,花环变为
aq
,是美观的; - $k=4$ 时,我们可以删除 $s[1,4]$,花环变为
q
,是美观的;
故我们的输出为 01011
。
样例输入 2
10
aabababbaa
样例输出 2
0000101011
样例输入 3
6
abcabc
样例输出 3
110111
数据范围
对于所有数据,$1 \leq n \leq 10^6$。
subtask1(10pts):$n \leq 100$;
subtask2(20pts):$n \leq 5000$;
subtask3(20pts):保证初始花环是美观的;
subtask4(50pts):无特殊限制。