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 ≤ i ≤ 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 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains two integers a and b (0 ≤ a, b ≤ 2 ⋅ 10^5, a + b ≥ 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 ⋅ 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


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


01011010
-1
0
-1
0110
-1
111
1001
0101010
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long int
#define ll long long
#define v4 vector<int>
#define v5 vector < v4 >
#define p4 pair<int,int>
#define F first
#define S second
#define mod 1000000007
#define all(c) c.begin(),c.end()
#define read(v) for(auto &it:v) cin>>it;
#define write(v) for(auto &it:v) cout<<it<<" ";
#define mwrite(m) for(auto &it:m) cout<<it.first<<" "<<it.second<<endl;
const int  N = 2e5 + 5;
void solve() 
{
   int a,b;
   cin>>a>>b;
   string s;
   cin>>s;
   int n=s.length();
   int zc=0,oc=0;
   int ck;
   if(a+b!=n)
   {
   	cout<<"-1"<<endl;
   	return;
   }
   if(n%2==0)
   	ck=n/2;
   else
   	ck=n/2+1;
   for(int i=0;i<ck;i++)
   {
   	  if(s[i]!=s[n-i-1] and s[i]!='?' and s[n-i-1]!='?')
   	  {
   	  	cout<<"-1"<<endl;
   	  	return;
   	  }
   	 if(s[i]=='0' || s[i]=='1' || s[n-i-1]=='0' || s[n-i-1]=='1')
   	 {
   	 	if(s[i]=='0' or s[n-i-1]=='0')
   	 	{
   	 		if(i==n-i-1)
   	 		{
   	 			zc+=1;
   	 		}
   	 		else
   	 			zc+=2;
   	 		s[i]='0';
   	 		s[n-i-1]='0';
   	 	}
   	 	else if(s[i]=='1' or s[n-i-1]=='1')
   	 	{
   	 		if(i==n-i-1)
   	 			oc+=1;
   	 		else
   	 			oc+=2;
   	 		s[i]='1';
   	 		s[n-i-1]='1';
   	 	}
   	 }
   	 //cout<<s<<endl;
   }
   // cout<<s<<endl;
   // cout<<zc<<" "<<oc<<endl;
   if((zc<a and oc>b) || (zc>a and oc<b))
   {
       cout<<"-1"<<endl;
       return;
   }
   else if(zc<=a and oc<=b)
   {
   	   int zl=a-zc;
       int ol=b-oc;
       //cout<<zl<<" "<<ol<<endl;
           for(int i=0;i<n;i++)
           {
           	 if(s[i]=='?' and zl>0)
           	 {
           	 	if(zl>1 and i!=n-i-1)
           	 	{
                  s[i]='0';
           	 	  s[n-i-1]='0';
           	 	  zl-=2;  
           	 	}
           	 	else if(zl==1 and i==n-i-1)
           	 	{
           	 		s[i]='0';
           	 		zl-=1;
           	 	}
           	 }
           	 else if(s[i]=='?' and ol>0)
           	 {
               if(ol>1 and i!=n-i-1)
           	 	{
                  s[i]='1';
           	 	  s[n-i-1]='1';
           	 	  ol-=2;  
           	 	}
           	 	else if(ol==1 and i==n-i-1)
           	 	{
           	 		s[i]='1';
           	 		ol-=1;
           	 	}
           	 }
           }
           //cout<<zl<<" "<<ol<<endl;
        if(zl==0 and ol==0)
        {
           cout<<s<<endl;
           return;
        }
        else
        {
            cout<<-1<<endl;
            return;
        }
   }

}
signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int  t;
    cin >> t;
    while (t--) solve();
    return 0;
}