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 PYTHON):

Solution:

s = raw_input()
t = raw_input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        if s[i - 1] == t[j - 1]:
            dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1])
        else:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])

l = dp[len(s)][len(t)]
resp = []
inds = len(s)
indt = len(t)
while len(resp) < l:
    if s[inds - 1] == t[indt - 1] and dp[inds][indt] == 1 + dp[inds - 1][indt - 1]:
        resp.append(s[inds - 1])
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt - 1]:
        inds -= 1
        indt -= 1
        continue
    if dp[inds][indt] == dp[inds - 1][indt]:
        inds -= 1
        continue
    if dp[inds][indt] == dp[inds][indt - 1]:
        indt -= 1
        continue
resp.reverse()
print(''.join(resp))