A Tide of Riverscape
Contest: Codeforces Round 487 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, strings

The records are expressed as a string $$$s$$$ of characters '0', '1' and '.', where '0' denotes a low tide, '1' denotes a high tide, and '.' denotes an unknown one (either high or low).

You are to help Mino determine whether it's possible that after replacing each '.' independently with '0' or '1', a given integer $$$p$$$ is not a period of the resulting string. In case the answer is yes, please also show such a replacement to Mino.

In this problem, a positive integer $$$p$$$ is considered a period of string $$$s$$$, if for all $$$1 \leq i \leq \lvert s \rvert - p$$$, the $$$i$$$-th and $$$(i + p)$$$-th characters of $$$s$$$ are the same. Here $$$\lvert s \rvert$$$ is the length of $$$s$$$.

Input format:
The first line contains two space-separated integers $$$n$$$ and $$$p$$$ ($$$1 \leq p \leq n \leq 2000$$$) — the length of the given string and the supposed period, respectively.

The second line contains a string $$$s$$$ of $$$n$$$ characters — Mino's records. $$$s$$$ only contains characters '0', '1' and '.', and contains at least one '.' character.

Output format:
Output one line — if it's possible that $$$p$$$ is not a period of the resulting string, output any one of such strings; otherwise output "No" (without quotes, you can print letters in any case (upper or lower)).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$7$$$ is not a period of the resulting string because the $$$1$$$-st and $$$8$$$-th characters of it are different.

In the second example, $$$6$$$ is not a period of the resulting string because the $$$4$$$-th and $$$10$$$-th characters of it are different.

In the third example, $$$9$$$ is always a period because the only constraint that the first and last characters are the same is already satisfied.

Note that there are multiple acceptable answers for the first two examples, you can print any of them.

Example input:
10 7
1.0.1.0.1.

Example output:
1000100010

Example input:
10 6
1.0.1.1000

Example output:
1001101000

Editorial:
Our very first observation is that when $$$p \leq \frac n 2$$$, the answer can never be "No".
Under this case, find any dot $$$s_i = \texttt{"."}$$$. At least one of $$$s_{i-p}$$$ and $$$s_{i+p}$$$ exists because $$$p \leq \frac n 2$$$ and $$$1 \leq i \leq n$$$. We want to make $$$s_i$$$ different from this character. In case this character is $$$\texttt{"0"}$$$ or $$$\texttt{"1"}$$$, replace the dot the other way round. In case it's a dot, replace the two dots differently with $$$\texttt{"0"}$$$ and $$$\texttt{"1"}$$$. After that, fill the remaining dots arbitrarily, and we obtain a valid answer.
If $$$p \gt \frac n 2$$$, we'd like to find a dot with a similiar property. That is, $$$s_i = \texttt{"."}$$$, and $$$s_{i-p}$$$ or $$$s_{i+p}$$$ exists. Go over all dots, try find one, and carry out the same operation as above. If no such dot exists, the answer is "No".
Bonus. Prove the time complexity of the seemingly-brute-force solution below.
Bonus. In case the answer is "Yes", find the lexicographically smallest string that fulfill the requirements.
Bonus. Solve the bonus challenge with $$$n \leq 10^5$$$. (Estimated difficulty: Div. 2 C)