411. Petya the Hero

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Petya has come back from the Berland-Birland War, and now he is fond of gathering his friends and narrating his heroic deeds. You have probably heard the story telling that Petya, being isolated, captured two Birland officers single-handed, than, using their clothes and having got to know the password, penetrated into the army base of the enemy, forced the controlling system out of action and helped Berland army to seize the base. This story was also heard by Colonel Kruglyakovsky, who was especially interested in a detail. That is the way Petya managed to find out the password for entering the army base with his poor knowledge of Birland language. Called by the colonel young hero explained, that although Birland speech wasn't clear to him, it wasn't too difficult to write it down. At first Petya interrogated the captives and wrote down the speech of each one as a string of latin letters. He knew that Birland valid passwords could be read the same way in either direction, i.e. they were palindromes. So he had to use the program, searching for the longest common substring of two strings, which was valid as a password. After hearing the answer, Colonel Kruglyakovsky declared, that this program could be very useful for interrogation captives and for decoding secret messages... As far as Petya certanly hadn't any program, he asked you for help.
Input
The input file contains two non-empty strings that consist of lowercase latin letters (
'a'
-
'z'
). The length of each string doesn't exceed 2000 symbols. The strings contain at least one common letter.
Output
Output the password obtained by the program Petya has described. If there are several possible passwords, output any of them.
Example(s)
sample input
sample output
abacaba
abracab
aca

sample input
sample output
abbab
babbab
abba


Online Contester Team © 2002 - 2010. All rights reserved.