В системе сравнения текстов анализируются две строки s и t. Система умеет находить общую подпоследовательность — последовательность символов, которая встречается в обеих строках в одинаковом относительном порядке, но не обязательно подряд.

Требуется вывести любую наибольшую общую подпоследовательность строк s и t. Если общих символов нет, выведите пустую строку.

Входные данные

Первая строка содержит строку s, вторая строка содержит строку t.

Обе строки непустые, состоят из строчных латинских букв.

Выходные данные

Выведите любую наибольшую общую подпоследовательность строк s и t.

Если такой подпоследовательности нет, выведите пустую строку.

Ограничения

• 1 <= |s|, |t| <= 1000
• строки состоят только из символов 'a'–'z'

Примеры

Пример 1

Входные данные

abcde
ace

Выходные данные

ace

Пояснение

Наибольшая общая подпоследовательность 'ace' имеет длину 3.

Пример 2

Входные данные

abc
ac

Выходные данные

ac

Пример 3

Входные данные

a
b

Выходные данные