C. 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 \leq i \leq 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

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

The first line of each test case contains two integers $a$ and $b$ ( $0 \leq a, b \leq 2 \cdot 10^{5}$ , $a + b \geq 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

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.

Example
inputCopy
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
outputCopy
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;
}