CF1265A.Beautiful String

A string is called beautiful if no two consecutive characters are equal. For example, "ababcb", "a" and "abab" are beautiful strings, while "aaaaaa", "abaa" and "bb" are not.

Ahcl wants to construct a beautiful string. He has a string $s$, consisting of only characters 'a', 'b', 'c' and '?'. Ahcl needs to replace each character '?' with one of the three characters 'a', 'b' or 'c', such that the resulting string is beautiful. Please help him!

More formally, after replacing all characters '?', the condition $s_i \neq s_{i+1}$ should be satisfied for all $1 \leq i \leq |s| - 1$, where $|s|$ is the length of the string $s$.

如果一个字符串中不存在两个相邻字符相等，则称该字符串为“优美的”。例如，“ababcb”、“a”和“abab”是优美的字符串，而“aaaaaa”、“abaa”和“bb”则不是。

Ahcl 想要构造一个优美的字符串。他有一个仅由字符 'a'、'b'、'c' 和 '?' 组成的字符串 $s$。Ahcl 需要将每个字符 '?' 替换为 'a'、'b' 或 'c' 中的一个，使得最终得到的字符串是优美的。请帮助他！

更准确地说，在将所有字符 '?' 替换完毕后，需满足对所有 $1 \leq i \leq |s| - 1$，均有 $s_i \neq s_{i+1}$，其中 $|s|$ 表示字符串 $s$ 的长度。

The first line contains positive integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Next $t$ lines contain the descriptions of test cases.

Each line contains a non-empty string $s$ consisting of only characters 'a', 'b', 'c' and '?'.

It is guaranteed that in each test case a string $s$ has at least one character '?'. The sum of lengths of strings $s$ in all test cases does not exceed $10^5$.

第一行包含一个正整数 $t$（$1 \leq t \leq 1000$）—— 表示测试用例的数量。接下来的 $t$ 行描述了各个测试用例。

每行包含一个非空字符串 $s$，该字符串仅由字符 'a'、'b'、'c' 和 '?' 组成。

保证在每个测试用例中，字符串 $s$ 至少包含一个字符 '?'。所有测试用例中字符串 $s$ 的长度总和不超过 $10^5$。

For each test case given in the input print the answer in the following format:

• If it is impossible to create a beautiful string, print "-1" (without quotes);
• Otherwise, print the resulting beautiful string after replacing all '?' characters. If there are multiple answers, you can print any of them.

对于输入中的每个测试用例，请按以下格式输出答案：

• 如果无法构造出优美的字符串，则输出 \-1（不带引号）；
• 否则，输出将所有 '?' 字符替换后的优美字符串。如果存在多个可行答案，输出任意一个即可。

In the first test case, all possible correct answers are "ababcb", "abcacb", "abcbcb", "acabcb" and "acbacb". The two answers "abcbab" and "abaabc" are incorrect, because you can replace only '?' characters and the resulting string must be beautiful.

In the second test case, it is impossible to create a beautiful string, because the $4$-th and $5$-th characters will be always equal.

In the third test case, the only answer is "acbac".

在第一个测试用例中，所有可能的正确答案为 “ababcb”、“abcacb”、“abcbcb”、“acabcb” 和 “acbacb”。而答案 “abcbab” 与 “abaabc” 是错误的，因为您只能替换字符 ‘?’，且最终得到的字符串必须是优美的（beautiful）。

在第二个测试用例中，不可能构造出优美的字符串，因为第 $4$ 个和第 $5$ 个字符必然相等。

在第三个测试用例中，唯一答案是 “acbac”。