String generation

Problem Statement

String Generation Problem Description You are given a pattern string S1 of length L1 , made of uppercase English letters, and a control string S2 of length L2 , made only of the characters T and F . Build a string S of length L1 + L2 - 1 , made of uppercase English letters, such that for every index i with 0 <= i < L2 : if S2[i] is T , the substring of S of length L1 starting at index i is equal to S1 ; if S2[i] is F , the substring of S of length L1 starting at index i is not equal to S1 . Among all strings S that satisfy every condition, print the lexicographically smallest one. If no such string exists, print -1 . Complete the function solve(S1, S2) , which returns the required string, or "-1" when no valid string exists. Input Format Read from standard input. T S1 S2 ... Line 1 contains the integer T , the number of test cases. Each test case is given on two lines: the first holds the string S1 and the second holds the string S2 . Output Format For each test case, print on it