1512_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 ≤ 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
```python
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    a,b=map(int,input().split())
    s=list(input().rstrip())
    l=len(s);question=s.count('?')
    f=0
    for i in range(0,l//2):
        left=s[i];right=s[l-1-i]
        if left==right:
            if left=='0':a-=2
            elif left=='1':b-=2
        elif left=='?':
            question -= 1
            if right=='0':a-=2;s[i]='0'
            else: b-=2;s[i]='1'
        elif right=='?':
            question -= 1
            if left=='0':a-=2;s[l-1-i]='0'
            else: b-=2;s[l-1-i]='1'
        else:print(-1);f=1;break

    if f==0:
        if l%2==1:
            if s[l//2]=='0':a-=1;
            elif s[l//2]=='1':b-=1;
            else:
                if a%2==1:a-=1;s[l//2]='0';question-=1;
                elif b%2==1:b-=1;s[l//2]='1';question-=1;
                else:print(-1);continue

        if a<0 or b<0 or a%2==1 or b%2==1 or a+b!=question:print(-1);continue

        for i in range(0, l // 2):
            if s[i]=='?':
                if a>0:s[i]=s[l-1-i]='0';a-=2
                else:s[i]=s[l-1-i]='1';b-=2

        for x in s:print(x,end="")
        print()













    
```