题目描述

在一个平面直角坐标系上有一个机器人。初始时机器人位于 $(0,0)$，Yuki 想要通过一系列指令使机器人到达 $(x,y)$。

具体而言，一个指令串为仅包含 $\texttt{01}$ 的字符串：

• $\texttt{0}$ 表示向右移动一步，即令机器人的位置由 $(a,b)$ 变为 $(a+1,b)$。
• $\texttt{1}$ 表示向上移动一步，即令机器人的位置由 $(a,b)$ 变为 $(a,b+1)$。

现在，Yuki 有一个仅包含 $\texttt{012}$ 的长度为 $n$ 的指令串 $s=s_1\dots s_n$。Yuki 需要先将这个指令串的 $\texttt{2}$ 都替换成 $\texttt{0}$ 或 $\texttt{1}$，然后机器人会按照如下规则进行操作：

• 对于每个非负整数 $i$，在第 $i$ 秒时，若机器人不位于 $(x,y)$，则机器人会执行指令串的第 $((i \bmod n)+1)$ 个指令。

Yuki 希望找到一种替换方式，使得在机器人能够到达 $(x,y)$ 的基础上，指令串的字典序尽可能小。你需要帮助 Yuki 求出，字典序最小的满足条件的替换后的指令串，或报告不存在满足条件的指令串。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 $n, x, y$ $(1 \le n \le 10^6,\ 0 \le x, y \le 10^{18})$。
• 第二行包含一个长度为 $n$ 的字符串 $s$ $(s_i \in \{\texttt 0,\texttt 1,\texttt 2\})$。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行：

• 若不存在满足条件的指令串，则输出一个整数 $-1$。
• 若存在满足条件的指令串，则输出一个长度为 $n$ 的字符串，表示字典序最小的满足条件的替换后的指令串。

6
5 2 4
01111
5 3 3
02221
5 3 3
00022
6 1 0
011201
4 8 7
2020
5 0 0
22102

01111
00111
-1
011001
-1
00100

提示

对于第 $1$ 组测试数据：

• 初始时机器人位于 $(0,0)$，指令串为 $\texttt{01111}$。
• 按照操作规则，机器人会依次移动到 $(1,0),(1,1),(1,2),(1,3),(1,4),(2,4)$。
• 由于机器人到达了 $(2,4)$，故 $\texttt{01111}$ 是一个满足条件的替换后的指令串。可以证明，$\texttt{01111}$ 是字典序最小的满足条件的替换后的指令串，因此答案即为 $\texttt{01111}$。

对于第 $2$ 组测试数据：

• 初始时机器人位于 $(0,0)$，我们将指令串 $\texttt{02221}$ 替换为 $\texttt{00111}$。
• 按照操作规则，机器人会依次移动到 $(1,0),(2,0),(2,1),(2,2),(2,3),(3,3)$。
• 由于机器人到达了 $(3,3)$，故 $\texttt{00111}$ 是一个满足条件的替换后的指令串。可以证明，$\texttt{00111}$ 是字典序最小的满足条件的替换后的指令串，因此答案即为 $\texttt{00111}$。

对于第 $3$ 组测试数据：

• 可以证明，不存在任意一种指令串的替换方式能够使得机器人到达 $(3,3)$。