CF526D.Om Nom and Necklace

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 2_k_ + 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.

一天，奥姆·诺姆发现了一条由 $n$ 颗不同颜色珠子串成的线。他决定从这条线的开头截取若干颗珠子，制成一条珠链，送给他的女友奥姆·内莉。

奥姆·诺姆知道，他的女友喜爱优美的图案。因此，他希望珠链上的珠子能构成一种规则模式。一个珠子序列 $S$ 被称为规则的，当且仅当它可以表示为

$$S = A + B + A + B + A + \dots + A + B + A,$$

其中 $A$ 和 $B$ 是某些珠子序列，“$+$” 表示序列的拼接，该和式中恰好有 $2k+1$ 个加项，其中包含 $k+1$ 个 “$A$” 加项与 $k$ 个 “$B$” 加项，并按 $A, B, A, B, A, \dots, A, B, A$ 的交替顺序排列。奥姆·内莉知道她的朋友是一位热忱的数学家，因此她并不介意 $A$ 或 $B$ 是空序列。

请帮助奥姆·诺姆判断：他可以从找到的这串珠子中（至少截取一颗，也可能全部截取）以多少种方式截取开头的一段珠子，使得所截得的珠子序列构成一个规则模式。奥姆·诺姆在截取珠子时不改变它们原有的顺序。

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

第一行包含两个整数 $n$、$k$（$1 ≤ n, k ≤ 1 000 000$）——分别表示 Om Nom 找到的线上的珠子数量，以及上述正则序列定义中的数 $k$。

第二行包含一个由 $n$ 个小写拉丁字母组成的序列，表示珠子的颜色。每种颜色对应一个单独的字母。

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.

输出一个由 n 个 0 和 1 组成的字符串。位置 i（1 ≤ i ≤ n）处必须为 1，当且仅当前 i 个珠子构成一个规则序列；否则为 0。

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

在第一个样例测试中，前 6 颗珠子构成的序列是正则序列（此时可取 $A = \text{""}$，$B = \text{"bca"}$），前 7 颗珠子构成的序列也是正则序列（此时可取 $A = \text{"b"}$，$B = \text{"ca"}$）。

在第二个样例测试中，例如，前 13 颗珠子构成的序列是正则序列，此时可取 $A = \text{"aba"}$，$B = \text{"ba"}$。