C. A-B палиндром
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$, состоящая из символов '0', '1' и '?'. Вам необходимо заменить все символы '?' в строке $$$s$$$ на '0' или '1' так, чтобы строка стала палиндромом и чтобы в ней было ровно $$$a$$$ символов '0' и ровно $$$b$$$ символов '1'. Обратите внимание, что каждый из символов '?' вы заменяете независимо от других.

Строка $$$t$$$ длины $$$n$$$ называется палиндромом, если для всех $$$i$$$ ($$$1 \le i \le n$$$) верно равенство $$$t[i] = t[n-i+1]$$$.

Например, если $$$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$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$a+b$$$, состоящую из символов '0', '1' и '?'.

Гарантируется, что сумма длин строк $$$s$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите:

  • «-1», если нельзя заменить все символы '?' в строке $$$s$$$ на '0' или '1' так, чтобы строка стала палиндромом и чтобы в ней было ровно $$$a$$$ символов '0' и ровно $$$b$$$ символов '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
Выходные данные
01011010
-1
0
-1
0110
-1
111
1001
0101010