# Broken Life solution codechef

## Broken Life solution codechef

You are given two strings SS and AA of lengths NN and MM respectively.

• String SS contains characters from the set {?, a, b, c, d, e}{?, a, b, c, d, e}.
• String AA contains characters from the set {a, b, c, d, e}{a, b, c, d, e}.

Let SS′ denote the string formed by replacing all the ?? in SS using the characters from the set {a, b, c, d, e}{a, b, c, d, e}.
Construct SS′ such that AA is not a subsequence of SS′.

If multiple such SS′ exist, output any. If no such SS′ exists, print 1−1.

### Broken Life solution codechef

• The first line will contain TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers NN and MM – the lengths of strings SS and AA respectively.
• The second line of each test case contains string SS.
• The third line of each test case contains string AA.

### Output Format

For each test case, output any valid string SS′. If no such string exists, print 1−1.

### Broken Life solution codechef

• 1T10001≤T≤1000
• 1N,M1051≤N,M≤105
• Sum of NN over all test cases does not exceed 31053⋅105.
• Sum of MM over all test cases does not exceed 31053⋅105.

### Sample Input 1

2
4 2
?ab?
ba
4 2
a??b
ab

[Coding] Broken Life solution codechef
aabe
-1


### Explanation

Test case 11: Replace the ?? at indices 11 and 44 using characters aa and ee respectively. Both the characters belong to the set {a, b, c, d, e}{a, b, c, d, e}.
The string S=aabeS′=aabe. Note that no subsequence of SS′ is equal to baba.

Test case 22: There is no possible value of SS′ such that abab is not a subsequence of SS′.