Om Nom and Necklace

题面翻译

已知长度为 $n$ 的字符串 $s$，对于 $s$ 的每一个前缀子串（即对于每一个 $i$，$s$ 中从第 $1$ 个字符到第 $i$ 个的所有字符组成的字符串，$1\leq i\leq n$），如果满足 $\texttt{ABABA...BA}$ 的形式（$A$、$B$ 可以为空，也可以是一个字符串，$A$ 有 $k+1$ 个，$B$ 有 $k$ 个），则请输出 $1$；否则输出 $0$，注意：$n$ 和 $k$ 给定。

题目描述

One day Om Nom found a thread with $n$ beads of different colors. He decided to cut the first several beads from this thread to make a bead necklace and present it to his girlfriend Om Nelly.

Om Nom knows that his girlfriend loves beautiful patterns. That's why he wants the beads on the necklace to form a regular pattern. A sequence of beads $S$ is regular if it can be represented as $S=A+B+A+B+A+...+A+B+A$ , where $A$ and $B$ are some bead sequences, " $+$ " is the concatenation of sequences, there are exactly $2k+1$ summands in this sum, among which there are $k+1$ " $A$ " summands and $k$ " $B$ " summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn't mind if $A$ or $B$ is an empty sequence.

Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn't change their order.

输入格式

The first line contains two integers $n$ , $k$ ( $1<=n,k<=1000000$ ) — the number of beads on the thread that Om Nom found and number $k$ from the definition of the regular sequence above.

The second line contains the sequence of $n$ lowercase Latin letters that represent the colors of the beads. Each color corresponds to a single letter.

输出格式

Print a string consisting of $n$ zeroes and ones. Position $i$ ( $1<=i<=n$ ) must contain either number one if the first $i$ beads on the thread form a regular sequence, or a zero otherwise.

样例 #1

样例输入 #1

7 2
bcabcab

样例输出 #1

0000011

样例 #2

样例输入 #2

21 2
ababaababaababaababaa

样例输出 #2

000110000111111000011

提示

In the first sample test a regular sequence is both a sequence of the first 6 beads (we can take $A=$ "", $B=$ "bca"), and a sequence of the first 7 beads (we can take $A=$ "b", $B=$ "ca").

In the second sample test, for example, a sequence of the first 13 beads is regular, if we take $A=$ "aba", $B=$ "ba".