← 返回题目列表

Codeforces · 1512/C

C. A-B 回文

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,由字符“0”、“1”和“?”组成。您需要将所有字符替换为“?”在字符串 $$$s$$$ 中添加“0”或“1”,以便该字符串成为回文,并且恰好包含 $$$a$$$ 字符“0”和 $$$b$$$ 字符“1”。请注意每个字符“?”独立于其他的被替换。

如果等式 $$$t[i] = t[n-i+1]$$$ 对于所有 $$$i$$$ ($$$1 \le i \le n$$$) 成立,则长度为 $$$n$$$ 的字符串 $$$t$$$ 称为回文。

例如,如果 $$$s=$$$"01??????0"、$$$a=4$$$ 和 $$$b=4$$$,则可以替换字符 '?'通过以下方式:

- "01011010";
- "01100110".

对于给定的字符串 $$$s$$$ 和数字 $$$a$$$ 和 $$$b$$$,将所有字符替换为 '?'在字符串 $$$s$$$ 中添加“0”或“1”,以便该字符串成为回文,并且恰好包含 $$$a$$$ 字符“0”和 $$$b$$$ 字符“1”。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$0 \le a, b \le 2 \cdot 10^5$$$, $$$a + b \ge 1$$$)。

每个测试用例的第二行包含长度为 $$$a+b$$$ 的字符串 $$$s$$$,由字符“0”、“1”和“?”组成。

保证所有测试用例中$$$s$$$的字符串长度总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出:

- “-1”,如果无法替换所有字符“?”在字符串 $$$s$$$ 中添加 '0' 或 '1',以便该字符串成为回文,并且它恰好包含 $$$a$$$ 字符 '0' 和 $$$b$$$ 字符 '1';
- 作为替换结果获得的字符串,否则。

如果有多种合适的方法来替换字符,则可以输出任何一种。

示例

输入 #1

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

输出 #1

01011010
-1
0
-1
0110
-1
111
1001
0101010