题目背景

淡い夕暮れ飲み込まれて
「君」の消えかけて姿を
忘れさせるように走ってた
新しい平和の世界に
——《心の記憶》

题目描述

• 本题中「子串」的定义如下：

字符串 $S$ 的子串是 $S$ 中连续的任意个字符组成的字符串。$S$ 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S(l,r)$（$1 \leq l \leq r \leq |S |,|S|$ 表示 $S$ 的长度）。

• 本题中「子序列」的定义如下：

对于字符串 $S$ 和一个长度为 $n$ 的严格单调递增数列 $k_1,k_2,\cdots,k_n(\forall 1\le i\le n,1\le k_i\le |S|)$，$S_{k_1},S_{k_2},\cdots,S_{k_n}$ 所组成的字符串即为 $S$ 的子序列。

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

• $B$ 是长度为 $m$ 的 01 串。
• $B$ 中不存在任意一个子串与 $A$ 相同。
• $B$ 中存在至少一个子序列与 $A$ 相同。

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

输入格式

第一行，一个正整数：$T$，表示询问次数。

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

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

输出格式

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

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

-1
01110
10100101
111101

提示

样例解释

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

数据范围

对于 $100\%$ 的数据，$1\le n\le m$，$1\le \sum m\le 2\times 10^6$。保证 $A$ 只由 0 和 1 组成。