Background

The pale dusk was swallowed up.
I ran as if to make you forget.
Your fading figure.
Into a new peaceful world.
——Heart no Kioku

Problem Description

• In this problem, the definition of a "substring" is as follows:

A substring of a string $S$ is a string formed by any number of consecutive characters in $S$. A substring of $S$ can be represented by a starting position $l$ and an ending position $r$, denoted as $S(l,r)$ ($1 \leq l \leq r \leq |S|$, where $|S|$ denotes the length of $S$).

• In this problem, the definition of a "subsequence" is as follows:

For a string $S$ and a strictly increasing sequence of length $n$, $k_1,k_2,\cdots,k_n(\forall 1\le i\le n,1\le k_i\le |S|)$, the string formed by $S_{k_1},S_{k_2},\cdots,S_{k_n}$ is a subsequence of $S$.

There are $T$ queries. In each query, you are given a binary string of length $n$, denoted as $A$. Your answer should be a string $B$ such that:

• $B$ is a binary string of length $m$.
• There does not exist any substring in $B$ that is equal to $A$.
• There exists at least one subsequence in $B$ that is equal to $A$.

You may output any string $B$ that satisfies the requirements.

Input Format

The first line contains one positive integer $T$, indicating the number of queries.

For each query, the first line contains two positive integers $n,m$ ($n \le m$), representing the lengths of the binary strings $A,B$.

The second line contains a binary string $A$ of length $n$.

Output Format

Output $T$ lines in total. Each line contains a binary string $B$ of length $m$. If there is no solution, output -1.

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

-1
01110
10100101
111101

Hint

Sample Explanation

In the second query, 01101 and 10110 are also valid solutions.

Constraints

For $100\%$ of the testdata, $1\le n\le m$, $1\le \sum m\le 2\times 10^6$. It is guaranteed that $A$ consists only of 0 and 1.

Translated by ChatGPT 5