C. A-B Palindrome Solution | CodeForces Round 713 Div. 3

 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 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]$�[�]=�[�-�+1]$ is true for all i$�$ (1≤i≤n$1\le �\le �$).

For example, if s=$�=$"01?????0", a=4$�=4$ and b=4$�=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≤t≤104$1\le �\le {10}^4$). Then t$�$ test cases follow.

The first line of each test case contains two integers a$�$ and b$�$ (0≤a,b≤2⋅105$0\le �,�\le 2\cdot {10}^5$, a+b≥1$�+�\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⋅105$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

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;

}