P9566 [SDCPC 2023] Difficult Constructive Problem

给定一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$，其中 $s_i \in \{\text{0}, \text{1}, \text{?}\}$，另外给定一个整数 $k$，请将字符串中所有的 $\text{?}$ 换成 $\text{0}$ 或 $\text{1}$，使得满足 $1 \le i < n$ 且 $s_i \ne s_{i+1}$ 的下标 $i$ 恰有 $k$ 个。不同的 $\text{?}$ 可以用不同字符替换。 为了让这题变得更加困难，我们要求您在答案存在的情况下，输出字典序最小的答案。 请回忆：称长度为 $n$ 的字符串 $a_1a_2\cdots a_n$ 的字典序小于长度为 $n$ 的字符串 $b_1b_2\cdots b_n$，若存在一个整数 $k$（$1 \le k \le n$）使得对于所有 $1 \le i < k$ 有 $a_i = b_i$，且 $a_k < b_k$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$0 \le k < n$）表示字符串的长度以及满足要求的下标数量。 第二行输入一个字符串 $s_1s_2,\cdots s_n$（$s_i \in \{\text{0}, \text{1}, \text{?}\}$）。 保证所有数据 $n$ 之和不超过 $10^6$。

每组数据输出一行。若答案存在则输出字典序最小的答案（您需要输出将 $\text{?}$ 替换之后的整个字符串，并让这个字符串的字典序最小），否则输出 `Impossible`。