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, t = input(), input()
ls, lt = len(s), len(t)

table = [[0] * (lt+1) for i in range(ls+1)]
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + ans

print(ans)