# C. A-B Palindrome

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

• "01011010";
• "01100110".

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

Input

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

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

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

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

Output

For each test case, output:

• "-1", if you can't replace all the characters '?' in the string $�$ by '0' or '1' so that the string becomes a palindrome and that it contains exactly $�$ characters '0' and exactly $�$ 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.

Example
input
Copy
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

output
Copy
01011010
-1
0
-1
0110
-1
111
1001
0101010
Solution:

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {
// take input
int a,b;
cin>>a>>b;

string s;
cin>>s;

int x=a,y=b;
// decrease count of current 0 and 1 from a and b
a-=count(s.begin(),s.end(),'0'),b-=count(s.begin(),s.end(),'1');

for(int i=0,j=s.length()-1; i<=j; i++,j--){
//if s is of odd length and in the middle there's ?
if(i==j && s[i]=='?'){
if(x%2){
s[i]='0';
a--;
}
else if(y%2){
s[i]='1';
b--;
}
}
// if both side there's ?
else if(s[i]=='?' && s[j]=='?')continue;
// if in the left its ? but not in right
else if(s[i]=='?'){
if(s[j]=='0' && a>0){
a--;
s[i]='0';
}
else if(s[j]=='1' && b>0){
b--;
s[i]='1';
}
}
// if in right its ? but not in left
else if(s[j]=='?'){
if(s[i]=='0' && a>0){
a--;
s[j]='0';
}
else if(s[i]=='1' && b>0){
b--;
s[j]='1';
}
}
}

// if theres odd number of ? then its not possible
if(count(s.begin(),s.end(),'?')%2){
cout<<-1<<endl;
return;
}

for(int i=0,j=s.length()-1; i<=j; i++,j--){
// if both left and right are ?
if(s[i]=='?'){
if(a>1){
a-=2;
s[i]='0',s[j]='0';
}
else if(b>1){
b-=2;
s[i]='1',s[j]='1';
}
// if a and b are less than 2 then its not possible to replce ?
else{
cout<<-1<<endl;
return;
}
}
}

// check for palindrome and a and b are equal to 0
for(int i=0,j=s.length()-1; i<=j; i++,j--)
if(s[i]!=s[j] || (a!=0 || b!=0)){
cout<<-1<<endl;
return;
}

cout<<s<<endl;

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

clock_t z = clock();

int t = 1;
cin >> t;
while (t--) solve();

return 0;
}