如果没有两个连续字符相等,则字符串被称为漂亮字符串。例如,“ababcb”、“a”和“abab”是漂亮的字符串,而“aaaaaa”、“abaa”和“bb”则不是。
Ahcl 想要构造一个漂亮的字符串。他有一个字符串 $$$s$$$,仅包含字符 'a'、'b'、'c' 和 '?'。 Ahcl 需要替换每个字符 '?'使用三个字符“a”、“b”或“c”之一,这样生成的字符串就很漂亮。请帮助他!
更正式地说,替换所有字符 '?' 后,所有 $$$1 \leq i \leq |s| 都应满足条件 $$$s_i \neq s_{i+1}$$$ - 1$$$,其中$$$|s|$$$ 是字符串$$$s$$$ 的长度。
输入
第一行包含正整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。接下来的 $$$t$$$ 行包含测试用例的描述。
每行包含一个非空字符串 $$$s$$$,仅由字符 'a'、'b'、'c' 和 '?' 组成。
保证在每个测试用例中字符串 $$$s$$$ 至少有一个字符“?”。所有测试用例中字符串$$$s$$$的长度总和不超过$$$10^5$$$。
输出
对于输入中给出的每个测试用例,按以下格式打印答案:
- 如果无法创建漂亮的字符串,则打印“-1”(不带引号);
- 否则,在替换所有 '?' 后打印生成的漂亮字符串字符。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 a???cb a??bbc a?b?c
输出 #1
ababcb -1 acbac
注意
在第一个测试用例中,所有可能的正确答案是“ababcb”、“abcacb”、“abcbcb”、“acabcb”和“acbacb”。两个答案“abcbab”和“abaabc”不正确,因为您只能替换“?”字符和生成的字符串必须是漂亮的。
在第二个测试用例中,不可能创建一个漂亮的字符串,因为第 $$$4$$$ 和第 $$$5$$$ 字符始终相等。
在第三个测试用例中,唯一的答案是“acbac”。