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 ≤ 1 000 000) — the number of beads on the thread that Om Nom found and number kfrom 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.

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".

大致题意：给一个字符串，问该字符串的[1,i]位上的字符串能不能由A+B+A+B+......+A构成？其中k+1个A,k个B,A,B可以为空串.

分析：分别枚举A,B不大好做，但是AB可以拼起来，原题就变成了能不能用k个AB和1个A拼成，AB作为一个循环节，要先求循环节的长度，利用kmp的next数组得到.最小循环节的t倍还是循环节，记作cir,那么问题就是判断能否存在t使得i / (t * cir) = k或i = (k+1) * t*cir

(A是空串).这个问题就比较简单了，将t用i,cir,k表示，检验t是否＞0并且满足条件式子.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n, k, nextt[];

char s[];

void init()

{

    int j = ;

    for (int i = ; i <= n; i++)

    {

        while (j >  && s[j + ] != s[i])

            j = nextt[j];

        if (s[j + ] == s[i])

            j++;

        nextt[i] = j;

    }

}

bool check(int x)

{

    int cir = x - nextt[x];

    if (x % (k + ) ==  && (x / (k + )) % cir == )

        return true;

    int t = x / (k * cir);

    if (t >  && x / (cir * t) == k)

        return true;

    return false;

}

int main()

{

    scanf("%d%d", &n, &k);

    scanf("%s", s + );

    init();

    for (int i = ; i <= n; i++)

    {

        if (check(i))

            printf("");

        else

            printf("");

    }

    return ;

}