题目背景

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

题目描述

小 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。

输入输出样例 #1

输入 #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。

该样例满足测试点 $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}

• 特殊性质 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$。

附件下载

string.zip 2.74KB