P9566 [SDCPC 2023] Difficult Constructive Problem

Given a string $s_1s_2\cdots s_n$ of length $n$ where $s_i \in \{\text{0}, \text{1}, \text{?}\}$ and an integer $k$, please fill out all the $\text{?}$ with $\text{0}$ or $\text{1}$ such that the number of indices $i$ satisfying $1 \le i < n$ and $s_i \ne s_{i+1}$ equals to $k$. Different $\text{?}$ can be replaced with different characters. To make this problem even more difficult, we ask you to find the answer with the smallest possible lexicographic order if it exists. Recall that a string $a_1a_2\cdots a_n$ of length $n$ is lexicographically smaller than another string $b_1b_2\cdots b_n$ of length $n$ if there exists an integer $k$ ($1 \le k \le n$) such that $a_i = b_i$ for all $1 \le i < k$ and $a_k < b_k$.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $0 \le k < n$) indicating the length of the string and the required number of indices satisfying the condition. The second line contains a string $s_1s_2,\cdots s_n$ ($s_i \in \{\text{0}, \text{1}, \text{?}\}$). It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

For each test case output one line. If the answer exists output the lexicographically smallest one (you need to output the whole given string after filling out all the $\text{?}$ and make this string the lexicographically smallest); Otherwise output `Impossible`.