有一天,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”。