You are given strings ~s~ and ~t~. Find one longest string that is a subsequence of both ~s~ and ~t~.

Notes

A subsequence of a string ~x~ is the string obtained by removing zero or more characters from ~x~ and concatenating the remaining characters without changing the order.

Constraints

• ~s~ and ~t~ are strings consisting of lowercase English letters.
• ~1 \le |s|, |t| \le 3000~

Input Specification

The first line of input will contain a string ~s~.

The second line of input will contain a string ~t~.

Output Specification

You are to print out, on a single line, one longest string that is a subsequence of both ~s~ and ~t~. If there are multiple such strings, any of them will be accepted.

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either one will be accepted.

Sample Input 2

aa
xayaz

Sample Output 2

aa

Sample Input 3

a
z

Sample Output 3

The answer is (an empty string).

Sample Input 4

abracadabra
avadakedavra

Sample Output 4

aaadara