%epigraph%%epigraphtext% _Walking along a riverside, Mino silently takes a note of something."Time," Mino thinks aloud.
"What?"
"Time and tide wait for no man," explains Mino. "My name, taken from the river, always reminds me of this."
"And what are you recording?"
"You see it, tide. Everything has its own period, and I think I've figured out this one," says Mino with confidence.
Doubtfully, Kanno peeks at Mino's records._%endepigraphtext%%endepigraph%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
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
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)).
[samples]
## 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.
Given:
- Integer $ n $: length of string $ s $.
- Integer $ p $: supposed period, $ 1 \leq p \leq n $.
- String $ s \in \{0, 1, .\}^n $, with at least one '.'.
Define:
A positive integer $ p $ is a **period** of string $ t $ of length $ n $ if for all $ i \in \{1, 2, \dots, n - p\} $, $ t[i] = t[i + p] $ (using 1-based indexing).
Objective:
Determine whether there exists a replacement of each '.' in $ s $ with either '0' or '1' such that $ p $ is **not** a period of the resulting string $ t $.
If yes, output any such $ t $; otherwise, output "No".
---
**Formal Constraints:**
Let $ t \in \{0,1\}^n $ be a string obtained by replacing each '.' in $ s $ with '0' or '1'.
We require:
There exists at least one index $ i \in \{1, 2, \dots, n - p\} $ such that $ t[i] \ne t[i + p] $.
Equivalently, we wish to **violate** the periodicity condition at least once.
Let $ I = \{ i \in \{1, \dots, n - p\} \mid s[i] \text{ and } s[i + p] \text{ are both fixed and different} \} $.
If $ I \ne \emptyset $, then $ p $ is already not a period → output $ s $ with all '.' replaced arbitrarily (e.g., all '0').
Otherwise, for all $ i \in \{1, \dots, n - p\} $, if $ s[i] $ and $ s[i + p] $ are both fixed, then they are equal.
Now consider the set of indices involved in period constraints:
Let $ G $ be the graph on indices $ \{1, 2, \dots, n\} $, where for each $ i \in \{1, \dots, n - p\} $, we connect $ i $ and $ i + p $.
This partitions the indices into $ p $ connected components (residue classes mod $ p $).
In each component, all positions must be equal if $ p $ is to be a period.
Let $ C_1, C_2, \dots, C_p $ be the connected components (each corresponds to $ i \mod p $).
In each component $ C_j $, if **all fixed characters** (non-'.' entries) are consistent (i.e., all same value), then we can assign that value to all '.' in the component to preserve periodicity.
But if **at least one component** contains **at least one '.'** and **no fixed character**, or **mixed fixed characters** (but we already assumed no fixed contradictions), then we can **break** periodicity by assigning two different values to two positions in the same component.
Wait — but if a component has **only one fixed character**, say '0', and other positions are '.', we can assign '0' to all → period holds.
But if a component has **at least two '.'** and **no fixed character**, then we can assign '0' to one and '1' to another → then for some $ i $, $ t[i] \ne t[i+p] $, so $ p $ is **not** a period.
Thus:
> **It is possible that $ p $ is not a period**
> **iff** there exists at least one connected component (mod $ p $) that contains **at least two positions** and **at least one '.'**, and **not all fixed characters in the component are forced to be equal** — but since we assume no fixed contradictions, the only way to break periodicity is if a component has **at least two '.'** (so we can assign them differently).
Actually, even if a component has **one fixed character and at least one '.'**, we can assign the '.' to be **different** from the fixed one → break periodicity.
So:
Let $ C $ be a component (i.e., a residue class mod $ p $).
- If $ C $ contains **any fixed character** (say '0'), and **at least one '.'**, then assign one '.' to '1' → violates $ t[i] = t[i+p] $ for some $ i $.
- If $ C $ contains **only '.'**, and has **at least two elements**, assign one '0' and one '1' → violates periodicity.
Only if **every component** has:
- All fixed characters equal (if any), and
- At most one '.' (so we cannot assign two different values)
→ then we are forced to assign all '.' consistently → period holds → output "No".
But note: if a component has exactly one '.' and one or more fixed characters, we must assign the '.' to match the fixed value → no choice.
So:
**Algorithm:**
1. For each residue class $ r \in \{0, 1, \dots, p-1\} $, collect all indices $ i \in \{1, \dots, n\} $ such that $ i \equiv r \pmod{p} $.
(Note: adjust to 0-based or 1-based consistently — we'll use 0-based indexing internally.)
2. For each such component:
- Let $ F $ be the set of fixed characters (non '.') in this component.
- If $ |F| \geq 1 $ and not all elements in $ F $ are equal → contradiction? But problem says: if fixed characters already violate, then p is not a period → we can output any replacement (e.g., replace all '.' with '0') and it’s already invalid.
So first, check:
For any $ i \in [0, n - p - 1] $, if $ s[i] \ne s[i + p] $ and both are not '.', then **p is already not a period** → output $ s $ with all '.' replaced by '0' (or any).
Otherwise, proceed.
3. For each component $ C $:
- Let $ \text{fixed\_val} = $ the value if all fixed characters are the same, else undefined (but we already checked above).
- Let $ \text{num\_dots} = $ number of '.' in $ C $.
If $ \text{num\_dots} \geq 1 $ and $ \text{fixed\_val} $ is defined → we can assign one '.' to $ \neg \text{fixed\_val} $ → break period.
If $ \text{num\_dots} \geq 2 $ and no fixed character → assign one '0', one '1' → break period.
If for **all** components: $ \text{num\_dots} = 0 $ or ($ \text{num\_dots} = 1 $ and $ \text{fixed\_val} $ exists) → then we have **no freedom** to break period → output "No".
Thus:
> **Output "No" if and only if**:
> For every component $ C $ (mod $ p $), either:
> - $ C $ has no '.', or
> - $ C $ has exactly one '.' and at least one fixed character (so the '.' must be assigned to match it).
> **Otherwise**, we can construct a string $ t $ that violates periodicity.
**Construction:**
- Start with $ t = s $, replace all '.' with '0' (default).
- Find a component $ C $ that allows a violation:
- Case 1: $ C $ has a fixed character '0' and at least one '.' → change one '.' in $ C $ to '1'.
- Case 2: $ C $ has no fixed character and at least two '.' → change one '.' to '1' (others remain '0').
Then output $ t $.
---
**Final Formal Output:**
Let $ s \in \{0,1,.\}^n $, $ p \in \mathbb{Z}^+ $, $ p \leq n $.
Define for $ r = 0 $ to $ p-1 $:
$ C_r = \{ i \in \{0, 1, \dots, n-1\} \mid i \equiv r \pmod{p} \} $
Let $ F_r = \{ s[i] \mid i \in C_r, s[i] \ne '.' \} $
If $ \exists r $, $ \exists i \in C_r $, $ j \in C_r $, $ i < j $, $ s[i], s[j] \in \{0,1\} $, $ s[i] \ne s[j] $:
→ Output $ s $ with all '.' replaced by '0'.
Else:
Let $ t $ be $ s $ with all '.' replaced by '0'.
If $ \exists r $ such that $ |F_r| = 0 $ and $ |C_r| \geq 2 $:
→ Change one '.' in $ C_r $ to '1' → output $ t $.
Else if $ \exists r $ such that $ |F_r| = 1 $ and $ |C_r| \geq 2 $:
→ Change one '.' in $ C_r $ to $ \neg F_r $ → output $ t $.
Else:
→ Output "No".
---
**Mathematical Formulation:**
Given:
- $ n, p \in \mathbb{Z}^+ $, $ 1 \leq p \leq n $
- $ s \in \{0,1,.\}^n $, with $ |\{ i \mid s[i] = . \}| \geq 1 $
Define:
For $ r \in \{0, 1, \dots, p-1\} $, let
$ C_r = \{ i \in \{0, \dots, n-1\} \mid i \equiv r \pmod{p} \} $
$ F_r = \{ s[i] \mid i \in C_r \text{ and } s[i] \ne '.' \} $
Define:
$ \text{Conflict} = \exists r, \exists i,j \in C_r \text{ s.t. } s[i], s[j] \in \{0,1\}, s[i] \ne s[j] $
If $ \text{Conflict} $:
Output: $ t $, where $ t[i] = \begin{cases} s[i] & \text{if } s[i] \ne '.' \\ 0 & \text{otherwise} \end{cases} $
Else:
Let $ t $ be as above.
If $ \exists r $ such that $ |F_r| = 0 $ and $ |C_r| \geq 2 $:
Let $ i_1, i_2 \in C_r $, $ s[i_1] = s[i_2] = '.' $, set $ t[i_1] = 1 $
Output $ t $
Else if $ \exists r $ such that $ |F_r| = 1 $ and $ |C_r| \geq 2 $:
Let $ f = \min(F_r) $, let $ i \in C_r $ with $ s[i] = '.' $, set $ t[i] = 1 - f $
Output $ t $
Else:
Output "No"