题目描述

• 本题中「子串」的定义如下： 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 l 与终止位置 r 来表示，记为$S(l,r)（1≤l≤r≤∣S∣,∣S∣ 表示 S 的长度$）。

• 本题中「子序列」的定义如下： 对于字符串 S 和一个长度为 n 的严格单调递增数列 $k1,k~2~,⋯,kn(∀1≤i≤n,1≤ki≤∣S∣)，Sk1,Sk2,⋯,Skn$ 所组成的字符串即为 S 的子序列。

现有 T 次询问。 每次询问给定一个长度为 n 的 01 串，记为 A。 回答应是一个字符串 B，满足：

• B 是长度为 m 的 01 串。

• B 中不存在任意一个子串与 A 相同。

• B 中存在至少一个子序列与 A 相同。

输出任意一个满足要求的字符串 B 即可。

输入格式

第一行，一个正整数：T，表示询问次数。 对于每一次询问，第一行两个正整数： n,m(n≤m)，分别表示 01 串 A,B 的长度。

第二行，一个长度为 n 的 01 串 A。

输出格式

共 T 行，每行一个长度为 m 的 01 串 B。无解则输出 -1。

输入输出样例

输入1

4
1 1
1
3 5
010
4 8
1101
5 6
11111

输出1

-1
01110
10100101
111101

说明/提示

样例解释 在第二次询问中，01101 和 10110 是另外合法的方案。

数据范围

| 子任务 | 分值 | ∑m≤ | 特殊性质 |

| 1 | 10 | $2×10^6$ | A只由0组成 |

| 2 | 10 | 15| 无 |

| 3 | 20 | 2000| 无 |

| 4 | 30 | $10^6$ | A随机生成 |

| 5 | 30 | $2×10^6$ | 无|

对于 100% 的数据，$1≤n≤m，1≤∑m≤2×10^6$。保证 A 只由 0 和 1 组成。$A~2~$ $u~i$,