A-B Palindrome
Contest: Codeforces Round 713 (Div. 3)
Difficulty rating: 1200
Tags: constructive algorithms, implementation, strings

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'.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
9
4 4
01?????0
3 3
??????
1 0
?
2 2
0101
2 2
01?0
0 1
0
0 3
1?1
2 2
?00?
4 3
??010?0

Example output:
01011010
-1
0
-1
0110
-1
111
1001
0101010

Editorial:
First, let's find such positions $$$i$$$ ($$$1 \le i \le n$$$) such that $$$s[i]\ne$$$'?' (symbols in symmetric positions are uniquely determined):
• If $$$s[n-i+1]=$$$'?', then $$$s[n-i+1] = s[i]$$$;
• If $$$s[i] \ne s[n-i+1]$$$, then at the end we will not get a palindrome in any way, so the answer is '-1'.
Note that after such a replacement, the remaining characters '?' are split into pairs, except maybe the central one. If the center character is '?' then it is necessary to put the character '0' if $$$a$$$ is odd, or '1' if $$$b$$$ is odd (if neither $$$a$$$, nor $$$b$$$ is odd, then the answer is '-1').
Now the remaining characters '?' are split into pairs (i.e. if $$$s[i]=$$$'?', then $$$s[n-i+1]=$$$'?'). This allows the remaining characters '0' and '1' to be replaced greedily:
• If $$$s[i]=$$$'?' and $$$a>1$$$, then $$$s[i]=s[n-i+1]=$$$'0' and decrease $$$a$$$ for $$$2$$$;
• If $$$s[i]=$$$'?' and $$$b>1$$$, then $$$s[i]=s[n-i +1]=$$$'1' and decrease $$$b$$$ for $$$2$$$;
• Otherwise the answer is '-1'.