You are given two strings S and A of lengths N and M respectively.
String S contains characters from the set \texttt{\{?, a, b, c, d, e\}}. 
String A contains characters from the set \texttt{\{a, b, c, d, e\}}. 

Let S' denote the string formed by replacing all the \texttt{?} in S using the characters from the set \texttt{\{a, b, c, d, e\}}.  
Construct S' such that A is not a [subsequence] of S'.

If multiple such S' exist, output any. If no such S' exists, print -1.

------ Input Format ------ 

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and M - the lengths of strings S and A respectively.
- The second line of each test case contains string S.
- The third line of each test case contains string A.

------ Output Format ------ 

For each test case, output any valid string S'. If no such string exists, print -1.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N,M ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.
- Sum of $M$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4 2
?ab?
ba
4 2
a??b
ab

----- Sample Output 1 ------ 
aabe
-1
----- explanation 1 ------ 
Test case $1$: Replace the $\texttt{?}$ at indices $1$ and $4$ using characters $\texttt{a}$ and $\texttt{e}$ respectively. Both the characters belong to the set $\texttt{\{a, b, c, d, e\}}$.  
The string $S' = \texttt{aabe}$. Note that no subsequence of $S'$ is equal to $\texttt{ba}$.

Test case $2$: There is no possible value of $S'$ such that $\texttt{ab}$ is not a subsequence of $S'$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms


Solutions:
def solve(S, A, m, n):
	S = list(S)
	(i, j) = (0, 0)
	while i < m and j < n:
		if S[i] == A[j]:
			j += 1
		elif S[i] == '?':
			if A[j] != 'a':
				S[i] = 'a'
			else:
				S[i] = 'e'
		i += 1
	if j < n:
		return ''.join(S)
	return -1
t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	S = input()
	A = input()
	print(solve(S, A, m, n))


def check(S, A):
	(n, m) = (len(S), len(A))
	S = list(S)
	(i, j) = (0, 0)
	while i < n and j < m:
		if S[i] == A[j]:
			j += 1
		elif S[i] == '?':
			if A[j] != 'a':
				S[i] = 'a'
			else:
				S[i] = 'e'
		i += 1
	if j < m:
		return ''.join(S)
	return -1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	S = input()
	A = input()
	print(check(S, A))


T = int(input())
for _ in range(T):
	(m, n) = map(int, input().split())
	s1 = input()
	s2 = input()
	s1 = list(s1)
	i = 0
	j = 0
	while i < m and j < n:
		if s1[i] == s2[j]:
			i += 1
			j += 1
		elif s1[i] == '?':
			if s2[j] != 'a':
				s1[i] = 'a'
			else:
				s1[i] = 'e'
			i += 1
		else:
			i += 1
	if j < n:
		print(''.join(s1))
	else:
		print(-1)


t = int(input())
for i in range(t):
	[n, m] = [int(x) for x in input().split(' ')]
	s = list(input())
	a = input()
	j = 0
	k = 0
	while j < n and k < m:
		if s[j] == a[k]:
			k += 1
		elif s[j] == '?':
			s[j] = 'e' if a[k] == 'a' else 'a'
		j += 1
	print('-1' if k == m else ''.join(s))