← 返回题目列表

Codeforces · 526/D

D. Om Nom 和项链

中文机器翻译题面 查看原题

有一天,Om Nom 发现了一根线,上面有 n 个不同颜色的珠子。他决定从这条线上剪下最初的几颗珠子,制作一条珠项链,并将其送给他的女朋友 Om Nelly。

Om Nom 知道他的女朋友喜欢漂亮的图案。这就是为什么他希望项链上的珠子形成规则的图案。如果一个珠子序列 S 可以表示为 S = A + B + A + B + A + ... + A + B + A,则它是规则的,其中 A 和 B 是一些珠子序列,“+”是序列的串联,这个和中正好有 2k + 1 个被加数,其中有 k + 1 个“A”被加数和 k 个“B”被加数交替排列。 Om Nelly 知道她的朋友是一位热心的数学家,所以她不介意 A 或 B 是否为空序列。

帮助 Om Nom 确定如何从找到的线中剪掉前几颗珠子(至少一颗;可能是全部),以便它们形成规则的图案。当 Om Nom 切断珠子时,他并没有改变它们的顺序。

输入

第一行包含两个整数 n, k (1 ≤ n, k ≤ 1 000 000) — Om Nom 找到的线上珠子的数量以及上面规则序列定义中的数字 k。

第二行包含 n 个小写拉丁字母的序列,代表珠子的颜色。每种颜色对应一个字母。

输出

打印由 n 个 0 和 1 组成的字符串。如果线程上的前 i 个珠子形成规则序列,则位置 i (1 ≤ i ≤ n) 必须包含数字 1,否则必须包含数字 0。

示例

输入 #1

7 2
bcabcab

输出 #1

0000011

输入 #2

21 2
ababaababaababaababaa

输出 #2

000110000111111000011

注意

在第一个样本测试中,常规序列既是前 6 个珠子的序列(我们可以取 A =“”,B =“bca”),又是前 7 个珠子的序列(我们可以取 A =“b”,B =“ca”)。

在第二个样本测试中,例如,前13个珠子的序列是规则的,如果我们取A =“aba”,B =“ba”。