Задача B1. Программирование робота ≡

Условие

Программа для робота X представляет из себя последовательность из 0 и 1. Известно, что если в коде содержится K подряд стоящих 0 или 1, то робот сбрасывается к заводским настройкам.

Вася написал программу для робота. В ходе написания программы часто допускаются ошибки, поэтому программа Васи может содержать K или более подряд идущих 0 или 1. Вася не хочет сброса настроек на роботе, но в тоже время он хочет как можно быстрее запустить свою программу. Для этого он хочет внести минимальное количество изменений в код программы, так чтобы программа не вызывала сброса настроек. Изменения бывают только двух видов: замена символа 1 на 0 и замена символа 0 на 1.

Программа Васи может быть достаточно длинной, поэтому он хочет автоматизировать процесс корректировки.

Формат входных данных

Первая строка входных данных содержит два целых числа n и k. Вторая строка входных данных содержит строку длины n, состоящую из 0 и 1.

Формат выходных данных

Выходные данные должны содержать одну строку длины n — откорректированную программу.

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ n, k ≤ 3 ⋅ 10⁵

Описание подзадач и системы оценивания

Решения, работающие для n ≤ 3, оцениваются из 20 баллов. Решения для n ≤ 10 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

Примеры тестов

3 3
111

110

10 3
1110001110

1100101100

3 3
101

101