给你一个只包含字符 '0', '1', 和 '?' 的字符串 ss。你需要用 '0' 或 '1' 替换 ss 中的所有 '?' 从而使得 ss 变成一个回文串并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1'. 注意每个字符 '?' 都是 独立于 其他字符被替换.

如果一个长度为 nn 的字符串 tt 对于所有的 i(1\le i\le n)i(1≤i≤n) 都满足 t[i]=t[n-i+1]t[i]=t[n−i+1] 那么 tt 被称为回文串

例如，如果 s=s="01?????0", a=4a=4 并且 b=4b=4, 那么你可以用以下方法替换 '?' :

• "01011010";
• "01100110".

对于给定的字符串 ss 以及整数 aa 和 bb, 用 '0' 或 '1' 替换 ss 中所有的 '?' 从而使的字符串 ss 回文 并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1'.

Input

第一行一个整数 tt (1 \le t \le 10^41≤t≤104). 下面是 tt 个测试样例.

每个测试样例第一行有两个整数 aa 和 bb (0 \le a, b \le 2 \cdot 10^50≤a,b≤2⋅105, a + b \ge 1a+b≥1).

每个测试样例第二行是一个长度为 a+ba+b 的字符串 ss, 包含字符 '0', '1', 和 '?'.

保证所有测试样例字符串 ss 的长度和不超过 2 \cdot 10^52⋅105.

Output

对每个测试样例输出:

• "-1", 如果你无法对于给定的字符串 ss 以及整数 aa 和 bb, 用 '0' 或 '1' 替换 ss 中所有的 '?' 从而使的字符串 ss 回文 并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1';
• 否则输出你替换所有的 '?' 且满足条件的字符串

如果有多个正确的构造方式，输出任意一个即可.

Input

9
4 5
?1???0110
1 1
??
0 1
?
2 2
0101
2 2
01?0
0 1
0
3 0
0?0
2 2
1??1
2 5
??010??

 

Output

011010110
-1
1
-1
0110
-1
000
1001
1101011

#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<math.h>
#include<stdlib.h>
int main()
{int t,i,j,a,b,a1,b1;int n,m;scanf("%d",&t);while(t--){a1=0;b1=0,c1=0;int flag=0;char s[410000];scanf("%d%d",&a,&b);getchar();scanf("%s",s);for(i=0;i<a+b;i++){if(s[i]=='1')b1++;//1的数量if(s[i]=='0')a1++;//0的数量}n=a+b;for(i=0;i<a+b;i++)//根据对称的那边构造回文数{if(s[i]=='1'&&s[n-i-1]=='?'){s[n-i-1]='1';b1++;}if(s[i]=='0'&&s[n-i-1]=='?'){s[n-i-1]='0';a1++;}}for(i=0;i<n;i++){if(s[i]!=s[n-1-i]){flag=1;break;}if(i==n-i-1&&s[i]=='?')//最后一项为？{if(a1<=a-1){s[i]='0';a1++;}else if(b1<=b-1){s[i]='1';b1++;}}if(s[i]=='?'&&s[n-i-1]=='?')//对称的两项都为？的情况{if(a1<=a-2)z{s[i]=s[n-i-1]='0';a1+=2;}else if(b1<=b-2){s[i]=s[n-i-1]='1';b1+=2;}}}if(a1==a&&b1==b&&flag==0){puts(s);}else{printf("-1\n");}}return 0;
}