P17295 [ICPC 2026 Xi'an I] Operating Robot

A robot is located on a 2D Cartesian coordinate system. Initially, the robot is at $(0,0)$, and Yuki wants to guide the robot to $(x,y)$ using a sequence of instructions. Specifically, an instruction string consists only of $\texttt{0}$ and $\texttt{1}$: - $\texttt{0}$ represents moving one step to the right, changing the robot's position from $(a,b)$ to $(a+1,b)$. - $\texttt{1}$ represents moving one step upward, changing the robot's position from $(a,b)$ to $(a,b+1)$. Yuki has an instruction string $s = s_1 \dots s_n$ of length $n$ containing only $\texttt{0}$, $\texttt{1}$, and $\texttt{2}$. Yuki must first replace all $\texttt{2}$s in the string with either $\texttt{0}$ or $\texttt{1}$. Then, the robot operates according to the following rule: - For every non-negative integer $i$, if the robot is not at $(x,y)$ at time $i$, the robot executes the $((i \bmod n) + 1)$-th instruction of the string. Yuki wants to find a replacement such that the robot reaches $(x,y)$ and the resulting instruction string is lexicographically as small as possible. You need to help Yuki find the lexicographically smallest instruction string that satisfies the condition, or report that no such string exists.

This problem contains multiple test cases. The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases. For each test case: - The first line contains three integers $n, x, y$ $(1 \le n \le 10^6,\ 0 \le x,y \le 10^{18})$. - The second line contains a string $s$ of length $n$ $(s_i \in \{\texttt 0,\texttt 1,\texttt 2\})$. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one line: - If no such instruction string exists, output $-1$. - If such an instruction string exists, output a string of length $n$ representing the lexicographically smallest valid instruction string.

For the first test case: - Initially, the robot is at $(0,0)$, and the instruction string is $\texttt{01111}$. - Following the rules, the robot moves sequentially to $(1,0), (1,1), (1,2), (1,3), (1,4), (2,4)$. - Since the robot reaches $(2,4)$, $\texttt{01111}$ is a valid instruction string. It can be proven that $\texttt{01111}$ is the lexicographically smallest valid string, so the answer is $\texttt{01111}$. \end{itemize} For the second test case: - Initially, the robot is at $(0,0)$, and we replace the instruction string $\texttt{02221}$ with $\texttt{00111}$. - Following the rules, the robot moves sequentially to $(1,0), (2,0), (2,1), (2,2), (2,3), (3,3)$. - Since the robot reaches $(3,3)$, $\texttt{00111}$ is a valid instruction string. It can be proven that $\texttt{00111}$ is the lexicographically smallest valid string, so the answer is $\texttt{00111}$. For the third test case: - It can be proven that there is no way to replace the $\texttt{2}$s in the instruction string such that the robot reaches $(3,3)$.