For each of the pairs of strings ( and ) received as input, find and print string on a new line. If you're able to form more than one valid string , print whichever one comes first alphabetically. If there is no valid answer, print instead.
The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:
The first line contains a single string denoting .
The second line contains a single string denoting .
and contain only lowercase English letters.
Sum of |a| over all queries does not exceed
Sum of |b| over all queries does not exceed
For each pair of strings ( and ), find some satisfying the conditions above and print it on a new line. If there is no such string, print instead.
We perform the following three queries:
Concatenate with to create .
We're given and ; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print .
Concatenate with to create . Note that we chose these particular substrings because the length of string must be maximal.