Generate Lexicographically Smallest String

String S1 of length L1 consisting of uppercase alphabets only. 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 (0 ≤ i < L2) is equal to S1 if and only if ith element of S2 is 'T'. If generating a string is not possible return -1.

Constraints

• 1 ≤ L1 ≤ 10⁴
• 1 ≤ L2 ≤ 100

Example 1

Input:

S1 = "ABCA"
S2 = "TFFF"

Output:

"ABCAAAA"

Explanation: S="ABCAAAA" is lexicographically smallest string that satisfies the given condition:-

• Character at index 0 of S2 = 'T' and Substring starting at index 0: "ABCA" is equal to S1.
• Character at index 1 of S2 = 'F'
• Character at index 2 of S2 = 'F'
• Character at index 3 of S2 = 'F'

Example 2

Input:

S1 = "ABA"
S2 = "TFT"

Output:

"ABABA"

Explanation: S="ABABA" is the lexicographically smallest string that satisfies the given condition.

Example 3

Input:

S1 = "ABC"
S2 = "TFT"

Output:

"-1"

Explanation: It is not possible to generate a string that satisfies the given condition, hence the output is -1.