Se te dan dos cadenas \(s\) y \(t\). Encontrá una cadena que sea la más larga posible y que sea subsecuencia tanto de \(s\) como de \(t\).

Nota: Una subsecuencia de una cadena \(x\) es la cadena que se obtiene al eliminar cero o más caracteres de \(x\) y concatenar los caracteres restantes sin cambiar el orden.

Entrada

La primera línea contiene la cadena \(s\). La segunda línea contiene la cadena \(t\).

\(s\) y \(t\) consisten de letras minúsculas del alfabeto inglés (\(1 \leq |s|, |t| \leq 3000\)).

Salida

Imprimir una subsecuencia común más larga de \(s\) y \(t\). Si hay múltiples respuestas, cualquiera de ellas será aceptada.

Ejemplo 1

Entrada

axyb
abyxb

Salida

axb

Nota: la respuesta puede ser axb o ayb; cualquiera será aceptada.

Ejemplo 2

Entrada

aa
xayaz

Salida

aa

Ejemplo 3

Entrada

a
z

Salida

Nota: la respuesta es la cadena vacía.

Ejemplo 4

Entrada

abracadabra
avadakedavra

Salida

aaadara