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

Constraints

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

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.

Examples

Input

axyb
abyxb


Output

axb


Input

aa
xayaz


Output

aa


Input

a
z


Output




Input

abracadabra
avadakedavra


Output

aaadara

Solution (in PYTHON3):

Solution:
s=input()
t=input()


dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
#dp[s][t]はs文字とt文字までのやつ

for sx in range(len(s)):
    for ty in range(len(t)):
        #sx+1文字目とty+1文字目が同じなら
        if s[sx]==t[ty]:dp[sx+1][ty+1]=dp[sx][ty]+1
        #違うならどっちか一つ削ったのと同じ
        else:dp[sx+1][ty+1]=max(dp[sx+1][ty],dp[sx][ty+1])


ans=''
i=len(s)
j=len(t)
while(i>0):
    if dp[i][j]==dp[i-1][j]:i-=1
    elif dp[i][j]==dp[i][j-1]:j-=1
    else:
        ans=t[j-1]+ans
        i-=1
        j-=1
print(ans)