Se us donen cadenes $s$ i $t$. Cerqueu una cadena més llarga que sigui una subseqüència de totes dues $s$ i $t$.

Una subseqüència d'una cadena $x$ és la cadena que s'obté eliminant zero o més caràcters de $x$ i concatenant els caràcters restants sense canviar l'ordre.

Entrada

L'entrada $1≤|s|,|t|≤3000$ es proporciona a partir de l'entrada estàndard en el format següent:

s
t

Sortida

Imprimiu una de les cadenes més llarga que sigui una subseqüència de $s$ i $t$. Si hi ha diverses cadenes d’aquest tipus, s’acceptarà la que abans aparegui a la primera frase.

Exemple d'entrada

bryf
bfyrf

Exemple de sortida

brf