Problem Brief

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.

1Example 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'

2Example 2

Input

S1 = "ABA", S2 = "TFT"

Output

"ABABA"

Explanation

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

3Example 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.

Constraints

Limits and guarantees your solution can rely on.

1 <= L1 <= 10^4
1 <= L2 <= 100

Draft autosaves locally

public String generateLexicographicallySmallestString(String S1, String S2) {
  // write your code here
}

Input

"ABCA"

"TFFF"

Output

"ABCAAAA"