New Fruit

Sanggeun merges the genes of two fruits to create a new one. If the merge succeeds, the new fruit tastes exactly like eating both fruits at the same time.

Before he starts, Sanggeun gives the new fruit a name. He could simply call the fruit made from an apple (apple) and a pear (pear) apple-pear, but such a name is not catchy.

Instead, he wants to name the new fruit with the shortest string that contains both fruit names as subsequences. A subsequence keeps the original order of the characters but does not have to be contiguous. For example, applear contains both apple (a, p, p, l, e) and pear (p, e, a, r) as subsequences, and it is the shortest string that does so.

Given the two fruit names, write a program that finds the name of the new fruit.

The input consists of several test cases. Each test case is given on a single line as the two fruit names to be merged, separated by a space. Each name consists of lowercase letters and has length at most 100. The input continues until end of file.

For each test case, print on its own line the shortest name that contains both fruit names as subsequences. If several names are tied for shortest, print the lexicographically smallest one.