Description

After finding her flowers, Jenny Cub encoded the locations of her flowers in a new set of maps and indices. Unfortunately, her mischievous brother Peter Bear decided to play a trick on her by adding additional letters to her encodings and jumbling them up. Dismayed, Jenny Cub once again needs your help to find the original encodings, so she can find her precious honey flowers.

This time, though, she has done some of the legwork and has grouped strings of encodings into pairs. Since Peter Bear isn't very creative, each word in the pair of encodings contains the original encoding; you just need to find the common permutation that appears in both encodings.

So, given a pair of encodings a and b, find the longest string x of letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Input

Jenny Cub has put all of the bad encodings in a list where each pair is on two consecutive lines. All the encodings consist of lowercase letters and are less than 128 characters long. Here is an sample input:

please
help
her
again
jennycub
loves
her
honey

Output

For each pair of encodings, print the original encoding if one is found. Otherwise, print out an empty line. Here is an sample output:

elp

e
eh

Approach

Sort both strings and find the common elements in both strings.

Input/Output

• Final Input: problem008.input
• Final Output: problem008.output

Source Code

• Peter Bui's source code: pbui.cc
• Noah Franske's source code: nfranske.cc
• Stephen Siena's source code: ssiena.cc