Problem Statement

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

Input

Input is given from Standard Input in the following format:
s
t

Output

Print one longest string that is a subsequence of both s and t.
If there are multiple such strings, any of them will be accepted.

Constraints

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

Sample Input 1

axyb
abyxb

Sample Output 1

axb

The answer is axb or ayb; either 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

见题面 Input 部分

见题面 Output 部分