P7814 "Little Nest R3" Heart no Kioku

> 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](https://music.163.com/song?id=1847928316)

- 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.

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 $T$ lines in total. Each line contains a binary string $B$ of length $m$. If there is no solution, output `-1`.

### Sample Explanation In the second query, `01101` and `10110` are also valid solutions. ### Constraints | Subtask | Score | $\sum m\le$ | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $2\times10^6$ | $A$ consists only of `0` | | $2$ | $10$ | $15$ | None | | $3$ | $20$ | $2000$ | None | | $4$ | $30$ | $10^6$ | $A$ is generated randomly | | $5$ | $30$ | $2\times 10^6$ | None | 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