给你一个只包含字符 '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';
- 否则输出你替换所有的 '?' 且满足条件的字符串
如果有多个正确的构造方式，输出任意一个即可.
Example
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<stdlib.h>
int main()
{int t,i,a,b;scanf("%d",&t);while(t--){ int a1=0,b1=0,c1=0,find=0,n;char s[400005];scanf("%d%d",&a,&b);getchar();scanf("%s",s);for(i=0;i<=a+b-1;i++){if(s[i]=='1')b1++;if(s[i]=='0')a1++;if(s[i]=='?')c1++;}n=a+b;for(i=0;i<=a+b-1;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]){find=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)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&&find==0) puts(s);else printf("-1\n");}return 0;
}