Given a string S1 of length L1 consisting of Latin uppercase alphabets only and a string S2 of length L2 consisting of characters 'T'and 'F' only.

Generate a lexicographically smallest string S of length (L1 + L2 - 1) such that a substring of length L1 in string S starting at index i (0 ≤ i < L2) is equal to S1 if and only if ith element of $2 is 'T (without quotes) else not.

If no such string can be generated, print "-1" (without quotes).

Notes

A string a is lexicographically smaller than a string b if and only if one of the following holds:

• a is a prefix of b, but a ‡ b;
• in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Find the lexicographically smallest string S which satisfies the given condition.

Function description

Complete the solve function. This function takes the following 2 parameters and returns the answer.

• S1: Represents a string ST
• S2: Represents a string S2

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing

34°C

Mostly cloudy

Search

New Sub

re

1

2

3

4

5

7

8

9

10 V

11

12

13

14

15

16

17

code in a language where we don't provide boilerplate code.

• The first line contains T, which represents the number of test cases.
• For each test case:
• The first line contains a string S1.
• The second line contains a string S2.

Output format

For each test case, print a string S in a new line or -1 if not possible.

Constraints

1 ≤ T ≤ 102

1≤IS11≤103

1 ≤ |S2 ≤ 103

Sample input E

1

ABCA

TFFF

Sample output

ABCAAAA

Answer rating: 100% (QA)

To solve this problem we can use the following algorithm Create a new string S of length L1 L2 1 Ini... View the full answer