Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. A-B Palindrome

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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:

- "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 \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$$$.

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

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

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2021 12:32:51 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|