#215704. [省选联考 2026] 摩卡串

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

小 H 有一个长度为 的 01 串 和一个正整数 。他定义一个长度为 的 01 串 为摩卡串，当且仅当 满足以下两个条件：

• 是 的子串，即存在 使得 ；
• 中恰好有 个子串的字典序严格小于 。两个子串不同当且仅当两个子串的长度不同或位置不同。形式化地，存在恰好 对 满足 且 的字典序严格小于 。

由于符合条件的摩卡串可能有很多，小 H 希望从中找出一个长度最短的摩卡串。你需要帮助他找出其中任意一个。

本题包含多组测试数据。

输入的第一行包含两个非负整数 ，分别表示测试点编号与测试数据组数。 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 。
• 第二行包含一个长度为 的 01 字符串 。

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

样例输入 1

0 5
1 1
1
1 1
0
3 9
101
4 17
1100
4 20
1100

样例输出 1

10
Impossible
0101
011100
001100

【样例 2】

见选手目录下的 string/string2.in 与 string/string2.ans。

该样例满足测试点 的约束条件。

【样例 3】

见选手目录下的 string/string3.in 与 string/string3.ans。

该样例满足测试点 的约束条件。

【样例 4】

见选手目录下的 string/string4.in 与 string/string4.ans。

该样例满足测试点 的约束条件。

【样例 5】

见选手目录下的 string/string5.in 与 string/string5.ans。

该样例满足测试点 的约束条件。

【样例 6】

见选手目录下的 string/string6.in 与 string/string6.ans。

该样例满足测试点 的约束条件。

【样例 7】

见选手目录下的 string/string7.in 与 string/string7.ans。

该样例满足测试点 的约束条件。

【数据范围】

对于所有测试数据，均有：

• ；
• ，；
• 对于所有 ，均有 。

::cute-table{tuack}

• 特殊性质 A：若存在摩卡串，则存在长度不超过 的摩卡串。
• 特殊性质 B：对于所有 ，均有 。
• 特殊性质 C：对于所有 ，均有 。
• 特殊性质 D：存在正整数 满足 且 。