Строка называется красивой, если никакие два последовательных символа строки не равны. Например, строки «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\).
Выходные данные
Для каждого тестового случая во входных данных выведите ответ в следующем формате:
- Если невозможно получить красивую строку, выведите «-1» (без кавычек);
- Иначе, выведите получившуюся красивую строку после замены всех символов '?'. Если существует несколько возможных ответов, вы можете найти любой из них.
Примечание
В первом тестовом случае, все возможные правильные ответы это «ababcb», «abcacb», «abcbcb», «acabcb» и «acbacb». Два ответа «abcbab» and «abaabc» являются неправильными, потому что можно заменять только символы '?' и получившаяся строка должна быть красивой.
Во втором тестовом случае, невозможно получить красивую строку, потому что \(4\)-й и \(5\)-й символы будут всегда совпадать.
В третьем тестовом случае, единственный возможный ответ это «acbac».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
a???cb
a??bbc
a?b?c
|
ababcb
-1
acbac
|