A14221 | A-B Palindrome

You are given a string $s$ consisting of the characters '0', '1', and '?'. You need to replace all the characters with '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and has exactly $a$ characters '0' and exactly $b$ characters '1'. Note that each of the characters '?' is replaced independently from the others.

A string $t$ of length $n$ is called a palindrome if the equality $t[i] = t[n-i+1]$ is true for all $i$ ( $1 \le i \le n$ ).

For example, if $s=$ "01?????0", $a=4$ and $b=4$ , then you can replace the characters '?' in the following ways:

- "01011010";
- "01100110".

For the given string $s$ and the numbers $a$ and $b$ , replace all the characters with '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and has exactly $a$ characters '0' and exactly $b$ characters '1'.

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ). Then $t$ test cases follow.

The first line of each test case contains two integers $a$ and $b$ ( $0 \le a, b \le 2 \cdot 10^5$ , $a + b \ge 1$ ).

The second line of each test case contains the string $s$ of length $a+b$ , consisting of the characters '0', '1', and '?'.

It is guaranteed that the sum of the string lengths of $s$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output:

- "-1", if you can't replace all the characters '?' in the string $s$ by '0' or '1' so that the string becomes a palindrome and that it contains exactly $a$ characters '0' and exactly $b$ characters '1';
- the string that is obtained as a result of the replacement, otherwise.

If there are several suitable ways to replace characters, you can output any.