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