P15650 [省选联考 2026] 摩卡串 / string

小摩卡是个天才，尤其在字符串理论方面有着异于常人的天赋。为了赞颂她的才华，人们常常将那些满足特定优美性质的字符串命名为“摩卡串”。

小 H 有一个长度为 $n$ 的 01 串 $s$ 和一个正整数 $k$。他定义一个长度为 $m$ 的 01 串 $t = t_1 \dots t_m$ 为**摩卡串**，当且仅当 $t$ 满足以下两个条件： - $s$ 是 $t$ 的子串，即存在 $1 \le l \le r \le m$ 使得 $s = t_l \dots t_r$； - $t$ 中恰好有 $k$ 个子串的字典序严格小于 $s$。两个子串不同当且仅当两个子串的长度不同或位置不同。形式化地，存在恰好 $k$ 对 $(l, r)$ 满足 $1 \le l \le r \le m$ 且 $t_l \dots t_r$ 的字典序严格小于 $s$。 由于符合条件的摩卡串可能有很多，小 H 希望从中找出一个**长度最短**的摩卡串。你需要帮助他找出其中任意一个。

**本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含两个正整数 $n, k$。 - 第二行包含一个长度为 $n$ 的 01 字符串 $s$。

对于每组数据，输出一行一个 01 字符串，表示任意一个**长度最短**的摩卡串。特别地，若不存在摩卡串，则输出 `Impossible`。

### 【样例 2】 见选手目录下的 `string/string2.in` 与 `string/string2.ans`。 该样例满足测试点 $4 \sim 6$ 的约束条件。 ### 【样例 3】 见选手目录下的 `string/string3.in` 与 `string/string3.ans`。 该样例满足测试点 $7 \sim 9$ 的约束条件。 ### 【样例 4】 见选手目录下的 `string/string4.in` 与 `string/string4.ans`。 该样例满足测试点 $10 \sim 12$ 的约束条件。 ### 【样例 5】 见选手目录下的 `string/string5.in` 与 `string/string5.ans`。 该样例满足测试点 $13 \sim 15$ 的约束条件。 ### 【样例 6】 见选手目录下的 `string/string6.in` 与 `string/string6.ans`。 该样例满足测试点 $16 \sim 18$ 的约束条件。 ### 【样例 7】 见选手目录下的 `string/string7.in` 与 `string/string7.ans`。 该样例满足测试点 $19, 20$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1 \le t \le 5$； - $1 \le n \le 200$，$1 \le k \le 3,000$； - 对于所有 $1 \le i \le n$，均有 $s_i \in \{0, 1\}$。 ::cute-table{tuack} | 测试点编号 | $n \le$ | $k \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $15$ | $200$ | A | | $4 \sim 6$ | $50$ | $2,000$ | B | | $7 \sim 9$ | ^ | ^ | C | | $10 \sim 12$ | ^ | ^ | D | | $13 \sim 15$ | ^ | $500$ | 无 | | $16 \sim 18$ | $150$ | $2,000$ | ^ | | $19, 20$ | $200$ | $3,000$ | ^ | - 特殊性质 A：若存在摩卡串，则存在长度不超过 $15$ 的摩卡串。 - 特殊性质 B：对于所有 $1\le i\le n$，均有 $s_i=0$。 - 特殊性质 C：对于所有 $1\le i\le n$，均有 $s_i=1$。 - 特殊性质 D：存在正整数 $p\in [1,n]$ 满足 $s_1=\dots =s_p=0$ 且 $s_{p+1}=\dots =s_n =1$。