We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Build a Palindrome

Build a Palindrome

You have two strings, and . Find a string, , such that:

  • can be expressed as where is a non-empty substring of and is a non-empty substring of .
  • is a palindromic string.
  • The length of is as long as possible.

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.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line contains a single string denoting .
  2. The second line contains a single string denoting .

Constraints

  • and contain only lowercase English letters.
  • Sum of |a| over all queries does not exceed
  • Sum of |b| over all queries does not exceed

Output Format

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.

Sample Input

3
bac
bac
abc
def
jdfh
fds

Sample Output

aba
-1
dfhfd

Explanation

We perform the following three queries:

  1. Concatenate with to create .
  2. We're given and ; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print .
  3. Concatenate with to create . Note that we chose these particular substrings because the length of string must be maximal.