New Store Name

Time limit2sMemory limit512 MB

Summary

Split each of two short strings into two non-overlapping contiguous pieces so that A+C equals B+D, and output the lexicographically smallest longest result.

Level: Hard8 of 10
Topics: String, Brute force, Dynamic programming
Solved: No attempts yet

Problem

Kangho and Junkyu closed the stores they used to run on their own and opened a new store together.

Today they want to decide the name of the new store. Each of them still keeps the signboard of the old store, and they want to build the new name by cutting those signboards. The procedure is the following. Uppercase and lowercase letters count as different letters.

Cut two pieces out of Kangho's signboard. Each piece must be a non-empty contiguous substring, and the two pieces must not overlap on the signboard. For example, if the signboard reads "abCDeF", you can cut "bC" and "e", or "CDeF" and "ab". Cutting "aC" and "eF" is impossible because "aC" is not contiguous, cutting "abCD" and "" is impossible because one piece is the empty string, and cutting "DeF" and "CD" is impossible because the two pieces overlap. Call the strings cut from Kangho's signboard A and B.
Cut two pieces out of Junkyu's signboard by the same rule. Call those strings C and D.
A + C and B + D must be equal, and that string becomes the name of the new store. Here + means string concatenation.

Given the string X written on Kangho's signboard and the string Y written on Junkyu's signboard, write a program that finds the longest possible name of the new store. If several names share the longest length, choose the one that comes first in lexicographic order. Lexicographic order follows ASCII codes, so every uppercase letter comes before every lowercase letter.

Input

The first line contains the string X of Kangho and the string Y of Junkyu, separated by one space. The length of each string is between 1 and 47, and both consist only of uppercase and lowercase letters.

Output

Print the longest possible name of the new store. If several names share the longest length, print the one that comes first in lexicographic order.

If no name is possible, print -1.

Examples4

Example 1
Input
```
StoreOfKangho StoreOfJunkyu
```
Expected output
```
ou
```
Example 2
Input
```
KanghoAndKangho Kangho
```
Expected output
```
-1
```

Example 3

Input

KanghoLikesToPlayGames JunkyuAlsoLikesToPlayGames

Expected output

esToPlayGames

Example 4
Input
```
abacaba abacabadabacaba
```
Expected output
```
abaabacaba
```