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$.


-----Input-----

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$.


-----Output-----

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. 


-----Example-----
Input
3
a???cb
a??bbc
a?b?c

Output
ababcb
-1
acbac



-----Note-----

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".

Difficulty: interview

Starter code:

Solutions:
# @author 

import sys

class ABeautifulString:
    def solve(self):

        def get_not(arr):
            for x in ['a', 'b', 'c']:
                if x not in arr:
                    return x

            assert(False)

        for _ in range(int(input())):
            s = list(input())
            n = len(s)
            for i in range(n - 1):
                if s[i] == s[i + 1] and s[i] != '?':
                    print(-1)
                    break
            else:
                x = 3 * ord('a') + 1 +2
                for i in range(n):
                    if s[i] == '?':
                        if (i > 0 and i < n - 1):
                            s[i] = get_not([s[i - 1], s[i + 1]])
                        elif i == 0:
                            s[i] = get_not([s[i + 1]])
                        else:
                            s[i] = get_not([s[i - 1]])

                print(''.join(s))

solver = ABeautifulString()
input = sys.stdin.readline

solver.solve()


import sys
def I():
        return sys.stdin.readline().rstrip()

for _ in range( int(I()) ):
    s = I()
    l = []
    last = 0
    for i in range(len(s)):
        nxt = s[ i + 1 ] if i < len(s) - 1 else 0
        if s[ i ] == '?':
            for c in 'abc':
                if c != last and c != nxt:
                    l.append(c)
                    last = c
                    break
        else:
            if s[ i ] == nxt:
                print(-1)
                break
            l.append( s[ i ] )
            last = s[ i ]
    else:
        print("".join(l))


t=int(input())
for _ in range(t):
    s=input()
    a=[i for i in s]
    c=['a','b','c']
    ok=True
    if len(s)==1:
        if s=='?':
            print('a')
        else:
            print(s)
    else:
        for i in range(len(s)-1):
            if a[i] is not '?':
                if a[i]==a[i+1]:
                    ok=False
        if ok:
            for i in range(len(s)):
                if a[i]=='?':
                    if i==0:
                        for j in c:
                            if j is not a[i+1]:
                                a[i]=j
                                break
                    elif i==len(s)-1:
                        for j in c:
                            if j is not a[i-1]:
                                a[i]=j
                                break
                    else:
                        for j in c:
                            if j is not a[i-1] and j is not a[i+1]:
                                a[i]=j
                                break
            ok=True
            for i in range(len(s)-1):
                if a[i]==a[i+1]:
                    ok=False
                    break
            if ok:
                print("".join(a))
            else:
                print(-1)

        else:
            print(-1)

from math import *
from collections import *
import sys
sys.setrecursionlimit(10**9)

t = int(input())
for y in range(t):
	s = list(input())
	n = len(s)
	for i in range(n):
		if(s[i] == '?'):
			if(0 == n-1): s[i] = 'a'
			elif(i == 0):
				if(s[i+1] != 'a'):
					s[i] = 'a'
				elif(s[i+1] != 'b'):
					s[i] = 'b'
				else:
					s[i] = 'c'
			elif(i == n-1):
				if(s[i-1] != 'a'):
					s[i] = 'a'
				elif(s[i-1] != 'b'):
					s[i] = 'b'
				else:
					s[i] = 'c'
			else:
				if(s[i+1] != 'a' and s[i-1] != 'a'):
					s[i] = 'a'
				elif(s[i+1] != 'b' and s[i-1] != 'b'):
					s[i] = 'b'
				else:
					s[i] = 'c'
	flag = 0
	for i in range(1,n):
		if(s[i] == s[i-1]):
			flag = 1
			break
	if(flag == 1): print(-1)
	else: print("".join(s))




t = int(input())
letters = ['a','b','c']
for iTest in range(t):
    s = list(input())
    valid = True
    prev = ''
    for c in s:
        if c == prev and c != '?':
            valid = False
            break
        prev = c
    if not valid:
        print(-1)
        continue
    for i in range(len(s)):
        if s[i] != '?':
            continue
        ns = set()
        if i > 0:
            ns.add(s[i-1])
        if i < len(s)-1:
            ns.add(s[i+1])
        for l in letters:
            if l not in ns:
                s[i] = l
                break
    print("".join(s))


for i in range(int(input())):
    s=list(input())
    n=len(s)
    
    for i in range(n-1):
        if s[i]==s[i+1] and s[i]!="?":
            print(-1)
            break
    else:
        if n==1:
            if s[0]=="?":
                s[0]="a"
            print("".join(s))
            continue
        if s[0]=="?":
            for j in "abc":
                if s[1]!=j:
                    s[0]=j
                    break
                
            
        for i in range(1,n-1):
            if s[i]=="?":
                for j in "abc":
                    if s[i+1]!=j and s[i-1]!=j:
                        s[i]=j
                        break
            # print(s)        
        if s[-1]=="?":
            for j in "abc":
                if j!=s[-2]:
                    s[-1]=j
                    break
        print("".join(s))
        
                
            



# c a _ c
T = int(input())

for t in range(1, T + 1):
	# print('Case #' + str(t) + ': ', end = '')
	flag = True
	s = input()
	for i in range(len(s)):
		if s[i] == '?':
			for j in ['a', 'b', 'c']:
				if (i + 1 >= len(s) or j != s[i + 1]) and (i - 1 < 0 or j != s[i - 1]):
					s = s[:i] + j + s[i + 1:]
					break
		if (i + 1 < len(s) and s[i] == s[i + 1]) or (i - 1 >= 0 and s[i] == s[i - 1]):
			# print(i, s[i])
			flag = False
			break

	if flag:
		print(s)
	else:
		print(-1)

'''input
3
??
1?
1?
'''
from sys import stdin
def input():
    return stdin.readline()[:-1]


for _ in range(int(input())):
    s = list(input())
    for i in range(0, len(s)):
        if s[i] == '?':
            if i > 0:
                prev = s[i-1]
            else:
                prev = 'x'
            if i < len(s) - 1:
                post = s[i+1]
            else:
                post = 'x'
            for ch in list('abc'):
                if ch != prev and ch != post:
                    s[i] = ch
                    break
    correct = True
    for i in range(0, len(s) - 1):
        if s[i+1] == s[i]:
            correct = False

    print(''.join(s)) if correct else print(-1)





a = int(input())
for x in range(a):
    prev = ''
    next = ''
    str = input()
    res = []
    ch = 0
    for i in range(len(str)):
        if str[i] == prev:
            print(-1)
            ch = 1
            break
        if i+1!=len(str):
            next = str[i+1]
        if str[i] == '?':
            if 'a' != prev and 'a' !=next:
                res.append('a')
                prev = 'a'
            elif 'b' != prev and 'b' !=next:
                res.append('b')
                prev = 'b'
            elif 'c' != prev and 'c' !=next:
                res.append('c')
                prev = 'c'
        if str[i]=='a' or str[i]=='b' or str[i]=='c':
            prev = str[i]
            res.append(prev)
    if ch == 0:
        print(''.join(y for y in res))


#!/usr/bin/env python3
from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
for i in range(n):
    s = input().rstrip()
    ans = []
    ans.append("#")
    for ch in s:
        ans.append(ch)
    ans.append("#")
    ok = True
    for i in range(1, len(ans)-1):
        if ans[i] == ans[i+1] and ans[i] != "?":
            ok = False
            break
        if ans[i] != "?":
            continue
        if "a" not in ans[i-1] + ans[i+1]:
            ans[i] = "a"
        elif "b" not in ans[i-1] + ans[i+1]:
            ans[i] = "b"
        elif "c" not in ans[i-1] + ans[i+1]:
            ans[i] = "c"
    if ok:
        print("".join([item for item in ans[1:-1]]))
    else:
        print(-1)