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 = list(input())
t = list(input())

dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)]
num = []

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

ans = ''
i = len(s)
j = len(t)

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

print(ans[::-1])