给定一个字符串 $$$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