Background

Problem Number: $\textit{24}$

After some training by Shameimaru Aya, Cirno’s IQ finally increased by ⑨ points.

Now the terakoya is going to have another exam. Cirno used some methods to learn part of the information about the correct answers. Also, because she is “ice-smart”, she does not want her score improvement to be too obvious, so that the teacher, Kamishirasawa Keine, will pay special attention to her. Therefore, she came to you for help.

(Note: cheating in exams is wrong!)

Problem Description

There are $2 \cdot n$ multiple-choice questions, and each question has two options: $\text{A}$ and $\text{B}$. The correct answers can be represented as a string of length $2 \cdot n$.

Now you need to construct an answer sheet (also a string of length $2 \cdot n$) such that it contains exactly $a$ $\text{A}$’s, and compared with the correct answer string, your answer sheet has exactly $e$ wrong answers. If no such construction exists, report that there is no solution.

Note: For easier handling, this problem guarantees $e \le n$.

Formally, given $n, a, e$ and a binary string $s$ of length $2 \cdot n$, you need to construct a binary string $p$ of length $2 \cdot n$ that contains exactly $a$ characters equal to $\texttt 0$, such that

$$\left(\sum_{i=1}^{2\cdot n}[s_i\ne p_i]\right)=e,$$

where $[]$ denotes the Iverson Bracket. See the “Hint” in “Notes / Hints”.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains three integers $n, a, e$.
• The second line contains a string of length $2 \cdot n$, representing the answer string.

Output Format

Output a total of $T$ lines.

For each test case:

• If there is a solution, output one line containing a string of length $2 \cdot n$, representing the answer sheet you constructed.
• If there is no solution, output one line containing the string $\texttt{-1}$.

2
3 2 3
ABABBA
3 3 1
AAABBB

BBAABB
-1

Hint

Sample Explanation

For test case $1$, the answer sheet you construct, $\text{BB{\color{e74c3c}AA}BB}$, contains exactly $2$ $\text A$’s, and compared with the correct answer string it differs at exactly $3$ positions (i.e., there are $3$ wrong answers):

$$\text{{\color{e74c3c}A}BA{\color{e74c3c}B}B{\color{e74c3c}A}}\\ \text{{\color{52c41a}B}BA{\color{52c41a}A}B{\color{52c41a}B}}$$

So it satisfies the requirements.

For test case $2$, there is no valid construction.

Constraints

For $100\%$ of the data, $1 \le T \le 100$, $1 \le n \le 10^5$, $0 \le e \le n$, $0 \le a \le 2 \cdot n$.

Within a single test file, it is guaranteed that $\sum(2 \cdot n) \le 10^6$.

Hint

$\textbf{A. Iverson Bracket}$

The Iverson Bracket is a notation using square brackets: if the condition inside the brackets is true, it equals $1$; otherwise it equals $0$. More precisely,

$$[P]=\begin{cases}1, & \text{If }P\text{ is true,}\\0,&\text{Otherwise.}\end{cases}$$

Translated by ChatGPT 5