Вам дана строка \(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\), то можно заменить символы '?' следующими способами:
Для заданной строки \(s\) и чисел \(a\) и \(b\) замените все символы '?' в строке \(s\) на '0' или '1' так, чтобы строка стала палиндромом и чтобы в ней было ровно \(a\) символов '0' и ровно \(b\) символов '1'.
Выходные данные
Для каждого набора входных данных выведите:
- «-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
|
01011010
-1
0
-1
0110
-1
111
1001
0101010
|