D. Ам Ням и ожерелье
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз Ам Ням нашёл нитку с надетыми на неё n камешками разных цветов. Он решил отрезать первые несколько камней с этой нитки, чтобы сделать из них бусы и подарить своей подруге, Ам Нелли.

Ам Ням знает, что его подруга любит красивые узоры. Поэтому он хочет, чтобы камешки на бусах образовывали регулярный узор. Последовательность камешков S называется регулярной, если она представима в виде S = A + B + A + B + A + ... + A + B + A, где A и B — некоторые последовательности камешков, " + " обозначает конкатенацию последовательностей, слагаемых в этой сумме ровно 2k + 1, среди которых k + 1 слагаемое "A" и k слагаемых "B", причём слагаемые "A" и "B" чередуются. Ам Нелли знает, что её друг — увлекающийся математик, поэтому она с пониманием отнесётся, даже если какая-то из последовательностей A или B окажется пустой.

Помогите Ом Ному определить, какими способами из найденной им нитки можно отрезать первые несколько камешков (не менее одного; возможно, все) таким образом, чтобы они образовывали регулярный узор. Отрезая камешки, Ам Ням не меняет их порядок.

Входные данные

В первой строке следуют два целых числа n, k (1 ≤ n, k ≤ 1 000 000) — количество камешков на нитке, найденной Ам Нямом, и число k из определения регулярной последовательности выше.

Во второй строке записана последовательность из n строчных латинских букв, обозначающих цвета камешков. Каждый цвет обозначается своей буквой.

Выходные данные

Выведите строку из n нулей и единиц. Позиция i (1 ≤ i ≤ n) должна либо содержать единицу, если первые i камешков на нитке образуют регулярную последовательность, либо ноль в противном случае.

Примеры
Входные данные
7 2
bcabcab
Выходные данные
0000011
Входные данные
21 2
ababaababaababaababaa
Выходные данные
000110000111111000011
Примечание

В первом тесте из условия регулярной является как последовательность из первых 6 камешков (если взять A = "", B = "bca"), так и последовательность из первых 7 камешков (если взять A = "b", B = "ca").

Во втором тесте из условия, например, последовательность из первых 13 камешков является регулярной, если взять A = "aba", B = "ba".