H. Сама подпоследовательность

Даны два слова из строчных латинских букв. Найдите их наибольшую общую подпоследовательность.

Таких подпоследовательностей может быть несколько; выведите лексикографически наименьшую среди самых длинных. Сравниваются сами слова: abc меньше, чем abd, а ab меньше, чем abc.

Порядок здесь важнее, чем кажется: сначала выбирается наибольшая длина, и только среди подпоследовательностей этой длины — наименьшая по алфавиту.

Первая строка содержит первое слово, вторая — второе. Длина каждого от 1 до 1000.

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