Hide

Problem G
Nafnagift

Languages en is
/problems/nafnagift/file/statement/en/img-0001.jpg
Kitten by Kirgiz03, Pixabay
Being a parent isn’t always easy; your children scream constantly, not to mention the incessant pestering for candy at the grocery store. That is why you, a mother of two, have decided to buy a kitten as a means to ease the tension. But this has lead to another crisis: what should the little one be called. Both your children have come up with a name and it’s up to you to have the final say. You know your children will be satisfied if their candidate names are a subsequence of your final decision. For your sake the name should be as short as possible.

A string $t$ is a subsequence of a string $s$ if it is possible to attain $t$ by removing some (or none) of the letters in $s$. For example, the string snati is a subsequence of ísknattleikur.

Input

The input consists of two lines. Each line contains a string corresponding to the candidate names your children provided. The length of each string is at least $1$ and at most $n$ and contains only lower case letters of the English alphabet.

Output

The output should contain a name for the cat that both children are satisfied by. Of all possible names, print the shortest. If there are more than one name of equal shortest length, print any of them.

Scoring

Group

Points

Constraints

1

33

$n \leq 10$, the strings only contain the letters a and b

2

27

$n \leq 10$

3

40

$n \leq 10^3$

Sample Input 1 Sample Output 1
bjarki
bergur
bjaergurki
Sample Input 2 Sample Output 2
kisi
kisi
kisi
Sample Input 3 Sample Output 3
aaaaa
bb
aaaaabb