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 \le i \le n$$$).
For example, if $$$s=$$$"01?????0", $$$a=4$$$ and $$$b=4$$$, then you can replace the characters '?' in the following ways:
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'.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.
The first line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 2 \cdot 10^5$$$, $$$a + b \ge 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 \cdot 10^5$$$.
For each test case, output:
If there are several suitable ways to replace characters, you can output any.
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
01011010 -1 0 -1 0110 -1 111 1001 0101010
| Codeforces Round 713 (Div. 3) |
|---|
| Finished |
