На одному з уроків, вчитель помітив, що деякі роботи учнів схожі. Для того, щоб спростити пошук схожих фрагментів у роботах учнів, вчитель вирішив написати програму, яка б знаходила найдовшу спільну послідовність символів у двох рядках тексту. Допоможіть йому реалізувати відповідний алгоритм.

Вхідні дані

Вхідні дані представляють собою два рядки тексту (довжина рядка до 1000 символів).

Вихідні дані.

Найдовша спільна послідовність символів. Якщо таких декілька, виведіть першу з них в алфавітному порядку.