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

Problem GNafnagift

Input

Output

Scoring

Problem G
Nafnagift