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++