Codeforces Round 487 (Div. 2) |
---|
Закончено |
— Время, — вслух думает Мино.
— Что?
— Время не ждет. Приливы тоже, — объясняет Мино. — Мое имя всегда напоминает мне об этом.
— Что же ты записываешь?
— Приливы, ты же видишь. У всего есть свой период, и мне кажется, этот я нашел, — уверенно заявил Мино.
Канно не уверен в записях Мино.
Заметки о приливе можно выразить как строку $$$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» (без кавычек, буквы можете выводить в любом регистре (строчные или заглавные)).
10 7
1.0.1.0.1.
1000100010
10 6
1.0.1.1000
1001101000
10 9
1........1
No
В первом примере $$$7$$$ не является периодом получившейся строки, так как $$$1$$$-й и $$$8$$$-й символы отличаются.
Во втором примере $$$6$$$ не является периодом получившейся строки, так как $$$4$$$-й и $$$10$$$-й символы отличаются.
В третьем примере $$$9$$$ всегда является периодом, потому что единственное условие для этого — совпадение первого и последнего символа — уже удовлетворено.
Обратите внимание, в первом и втором примере существует несколько правильных ответов, вы можете вывести любой.
Название |
---|