Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

题目描述

新年就要到了,小 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):无特殊限制。