Careful Declaration

Time limit2sMemory limit128 MB

Summary

Merge two word sequences into the shortest common supersequence, breaking ties by choosing the lexicographically smallest result.

Level: Hard8 of 10
Topics: Dynamic programming, String, Greedy, Implementation
Solved: No attempts yet

Problem

"Do not panic!" is not only the famous inscription on a book cover — it is also the message every bank must convey to its clients during any crisis, however small. If clients begin to panic, it can spell the end of a bank.

To reassure their clients, banks and governments issue declarations stating that there is nothing to worry about. For people to believe them, these declarations must be consistent with one another.

Suppose we have two declarations: one proposed by a bank and one by the government. They decide to merge the two into a single joint declaration and issue it together (too many separate declarations might itself look like a sign of trouble). Both parties insist that the combined declaration contain the entire text of their own original declaration.

Your task is to produce the joint declaration to be issued tonight. The result must contain every word of both original declarations in their original order, and it must be as short as possible.

Input

The input contains several test cases. Each test case consists of two lines of text giving the two original declarations. Each line contains at least $1$ and at most $2000$ words separated by single spaces. Every word consists of lowercase English letters (a–z), with at least $1$ and at most $10$ letters. After the last word of each declaration there is a single dot (.), preceded by one space.

A final line containing a single dot (.) follows the last test case.

Output

For each test case, output a single line containing a sequence of words separated by single spaces, with the following properties:

Both input declarations are subsequences of the output — every word of each original declaration appears in the result in the same order, though the two may be interleaved with each other.
Among all texts satisfying property 1, the output contains the fewest possible words.
If several texts share that minimum length, output the lexicographically smallest one.

After the last word, print a space and a single dot (.).

A text A is lexicographically smaller than a text B if it would come first in a dictionary: at the first position where the two texts differ, the word in A is lexicographically smaller than the word in B.

A word C is lexicographically smaller than a word D if either (a) at the first letter where they differ, C's letter comes earlier in the alphabet, or (b) C is shorter than D and is a prefix of D.

Examples4

Example 1

Input

all our banks are sound and safe .
all deposits in our bank are safe do not worry .
everything fine firmly under control .
deposits in bank abc are fine like nothing is .
.

Expected output

all deposits in our bank banks are sound and safe do not worry .
deposits everything in bank abc are fine firmly like nothing is under control .

Example 2
Input
```
hello .
hello .
.
```
Expected output
```
hello .
```
Example 3
Input
```
c b a .
z y x .
.
```
Expected output
```
c b a z y x .
```
Example 4
Input
```
a c e .
a b c d e .
.
```
Expected output
```
a b c d e .
```