题目描述

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.

题目大意

【题目描述】

给定一个长度为 $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。

5
9 6
1?010??01
9 5
1?010??01
9 6
100101101
9 5
100101101
9 3
????????1

100100101
Impossible
100101101
Impossible
000000101