Олимпиадный тренинг

Задача . B. Речной прилив


Прогуливаясь вдоль реки, Мино молча что-то записывает.

— Время, — вслух думает Мино.

— Что?

— Время не ждет. Приливы тоже, — объясняет Мино. — Мое имя всегда напоминает мне об этом.

— Что же ты записываешь?

— Приливы, ты же видишь. У всего есть свой период, и мне кажется, этот я нашел, — уверенно заявил Мино.

Канно не уверен в записях Мино.

Заметки о приливе можно выразить как строку \(s\) из символов «0», «1» и «.», где «0» означает отсутствие прилива, «1» означает наличие прилива, а «.» означает, что записей в этот день нет (возможно, прилив был, возможно, не было).

Вы должны помочь Мино определить, возможно ли, что после замены каждого символа «.» независимо на «0» или «1» данное число \(p\) не является периодом получившейся строки. Если ответ утвердительный, то найдите одну из таких возможных замен.

В данной задаче положительное целое число \(p\) является периодом строки \(s\), если для всех \(1 \leq i \leq \lvert s \rvert - p\) символы \(i\) и \((i + p)\) строки \(s\) совпадают. Здесь \(\lvert s \rvert\) обозначает длину строки \(s\).

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

Первая строка содержит два целых числа \(n\) и \(p\) (\(1 \leq p \leq n \leq 2000\)) — длину данной строки и период, который вам нужно проверить, соответственно.

Вторая строка содержит строку \(s\) из \(n\) символов — записи Мино. \(s\) содержит только символы «0», «1» и «.» и содержит как минимум один символ «.».

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

Выведите одну строку: если возможно, что \(p\) не является периодом строки после замены, выведите получившуюся строку после одной из таких замен; иначе выведите «No» (без кавычек, буквы можете выводить в любом регистре (строчные или заглавные)).

Примечание

В первом примере \(7\) не является периодом получившейся строки, так как \(1\)-й и \(8\)-й символы отличаются.

Во втором примере \(6\) не является периодом получившейся строки, так как \(4\)-й и \(10\)-й символы отличаются.

В третьем примере \(9\) всегда является периодом, потому что единственное условие для этого — совпадение первого и последнего символа — уже удовлетворено.

Обратите внимание, в первом и втором примере существует несколько правильных ответов, вы можете вывести любой.


Примеры
Входные данныеВыходные данные
1 10 7
1.0.1.0.1.
1000100010
2 10 6
1.0.1.1000
1001101000
3 10 9
1........1
No

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя