Задано два рядки \(S\) та \(T\). Знайдіть їх найдовшу спільну підпослідовність. (іншими словами, необхідно з кожного слова викреслити 0 або більше символів так, щоб рядки які залишились були ідентичні і мали якомога більшу довжину).

Формат вхідних даних

В двох окремих рядках міститься по слову, які складаються з маленьких латинських літер. Довжина слів до 3000 символів.

Формат вихідних даних

Виведіть найдовшу спільну послідовність (якщо відповідей декілька - виведіть будь-яку).

Приклад вхідних даних-1

axyb
abyxb

Приклад вихідних даних-1

axb

Пояснення до прикладу-1

можливі відповіді axb та ayb

Приклад вхідних даних-2

aa
xayaz

Приклад вихідних даних-2

aa

Приклад вхідних даних-3

a
z

Приклад вихідних даних-3

Пояснення до прикладу-3

відповідь - пустий рядок

Приклад вхідних даних-4

abracadabra
avadakedavra

Приклад вихідних даних-4

aaadara