A. Красивая строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка называется красивой, если никакие два последовательных символа строки не равны. Например, строки «ababcb», «a» и «abab» красивые, тогда как «aaaaaa», «abaa» и «bb» нет.

Ahcl хочет построить красивую строку. У него есть строка $$$s$$$, состоящая только из символов 'a', 'b', 'c' и '?'. Ahcl должен поменять каждый символ '?' на один из трех символов 'a', 'b' или 'c', так что получившаяся строка будет красивой. Помогите ему!

Более формально, после замены всех символов '?', условие $$$s_i \neq s_{i+1}$$$ должно быть выполнено для всех $$$1 \leq i \leq |s| - 1$$$, где $$$|s|$$$ это длина строки $$$s$$$.

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

В первой строке находится положительное целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество тестовых случаев. Следующие $$$t$$$ строк содержат описания тестовых случаев.

Каждая строка содержит непустую строку $$$s$$$, состоящую только из символов 'a', 'b', 'c' и '?'.

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

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

Для каждого тестового случая во входных данных выведите ответ в следующем формате:

  • Если невозможно получить красивую строку, выведите «-1» (без кавычек);
  • Иначе, выведите получившуюся красивую строку после замены всех символов '?'. Если существует несколько возможных ответов, вы можете найти любой из них.
Пример
Входные данные
3
a???cb
a??bbc
a?b?c
Выходные данные
ababcb
-1
acbac
Примечание

В первом тестовом случае, все возможные правильные ответы это «ababcb», «abcacb», «abcbcb», «acabcb» и «acbacb». Два ответа «abcbab» and «abaabc» являются неправильными, потому что можно заменять только символы '?' и получившаяся строка должна быть красивой.

Во втором тестовом случае, невозможно получить красивую строку, потому что $$$4$$$-й и $$$5$$$-й символы будут всегда совпадать.

В третьем тестовом случае, единственный возможный ответ это «acbac».