Co ma babcia Bajtazara do darmowego kebaba?

Limit pamięci: 256 MB

-Co ma piernik do wiatraka?
-Wiatrak zawsze może się spierniczyć...

Bajtłomiej z Bajtoszem grali w zgadywanki. Pewnego razu Bajtosz zadał pytanie:
-Co ma babcia Bajtazara do darmowego kebaba?
-...?
-babar
W pierwzej chwili Bajtłomiej był lekko skonfundowany, jednak już w następnej chwili zrozumiał: babar to najdłuższy wspólny podciąg słów babciabajtazara i kebabdarmo! Po skończonej zabawie postanowił poćwiczyć, aby Bajtosz więcej go nie zaskoczył. W tym celu przez godzinę dziennie będzie szukać najdłużych wspólnych podciągów różnych słów. Pomóż mu!

Wejście

Wejścia składa się z dwóch wierszy. W każdym z nich znajduje się słowo podane przez Bajtłomieja, złożone z małych liter alfabetu angielskiego o długości nie większej niż 5000.

Wyjście

Na wyjście wypisz dwa wiersze. W pierszym powinna znajdować się liczba oznaczająca długość najdłuższego wspólnego podciągu podanych przez Bajtłomieja słów, w drugim zaś słowo będące tym podciągiem. Jeśli istnieje więcej niż jedna poprawna odpowiedź, wypisz dowolną z nich.

Przykład

Dla danych

babciabajtazara
kebabdarmo

Poprawnym wynikiem jest:

5
babar