P17295 [ICPC 2026 Xi'an I] Operating Robot

在一个平面直角坐标系上有一个机器人。初始时机器人位于 $(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$ 的字符串，表示字典序最小的满足条件的替换后的指令串。

对于第 $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)$。