C. A-B Palindrome
time limit per test
2 seconds
memory limit per test
256 megabytes
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≤104). Then t
test cases follow.
The first line of each test case contains two integers a
and b (0≤a,b≤2⋅105, 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⋅105
.
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103318.html
