Some problems are so classic that barely need a statement. For this one, we ask you to compute the longest subword that two given words have in common. In case of a tie, print the smallest one in alphabetical order.

Input

Input consists of several cases,
each with two non-empty words w_{1} and w_{2}
made up of at most 500 lowercase letters.

Output

For every case, print the longest common subword. In case of a tie, print the smallest one in alphabetical order.

Observation

There are very fast algorithms to solve this problem.
Here, we settle for one that takes time proportional to n_{1}· n_{2},
where n_{1} and n_{2} are the lengths of w_{1} and w_{2}.

Public test cases

**Input**

pseudopseudohypoparathyroidism floccinaucinihilipilification supercalifragilisticexpialidocious sipircilifrigilisticixpiilidiciiis supercalifragilisticexpialidocious zzz abczzzcdazzzaba abcxxxcdaxxxaba

**Output**

at gilistic aba

Information

- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++ Python