Problem D
Encryption

Boschua is not very good at cybersecurity. When he heard of the mantra “don’t roll your own cryptography”, he decided to ignore the “don’t”.

He has proposed a new encryption scheme based on subsequences. We say that a string $a$ is a subsequence of string $b$ if the string $a$ can be obtained by removing $0$ or more characters from $b$, while keeping the relative order of the characters. For example, hej, hejsan and jan are all subsequences of the word hejsan, while na is not.

His encryption scheme is as follows: to send a string $s$, you need a decoy string, $d$. Instead of sending $s$, you will send the shortest possible string that contains both $s$ and $d$ as subsequences. The hope is then that when looking at the sent string, unwanted parties will only notice the decoy $d$, not $s$. Compute the shortest common supersequence of $s$ and $d$ to carry out Boschua’s terrible encryption scheme.

Boschua also gives you the following string: the longest string that is a subsequence of both $s$ and $d$. If there are multiple such strings, you are given an arbitrary one of them. Apparently it’s a leftover from a previous project and might be useful.

Input

The first line of input contains the string $s$, consisting of lowercase letters a-z.

The second line of input contains the string $d$, consisting of lowercase letters a-z.

The third line of input contains the longest string that is a subsequence of both $s$ and $d$, consisting of lowercase letters a-z.

It is guaranteed that both $|s|, |d| \geq 1$, but the longest common subsequence might be empty.

Output

Print the shortest string where both $s$ and $d$ appear as subsequences. If there are multiple such strings, any will suffice.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Samples

In sample $1$, because $s$ and $d$ share no common characters, any solution must contain both of them fully.

In sample $2$, both $s$ and $d$ are subsequences of adbadc. First, abac can be obtained as follows: adbadc. Similarly, adbdc, can be obtained as follows: adbadc.

aaa
bbb

aaabbb

abac
adbdc
abc

adbadc