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

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

Ограничения

3 ≤ n, k ≤ 3 ⋅ 105

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

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

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

Стандартный вход Стандартный выход
1
3 3
111
110
2
10 3
1110001110
1100101100
3
3 3
101
101

0.080s 0.009s 13