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:
n=input()
m=input()
x=len(n)

y=len(m)

dp=[[0 for i in range(y+1)] for j in range(x+1)]
#print(len(dp),len(dp[0]))
for i in range(0,x+1):
  for j in range(0,y+1):
    if(i==0 or j==0):
      dp[i][j]=0
    elif n[i-1]==m[j-1]:
      dp[i][j]=1+dp[i-1][j-1]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i][j-1])
j=y
i=x
ans=""
#print(i,j)
while(i>0 and j>0):
  if dp[i][j]==dp[i-1][j]:
    i -= 1
  elif dp[i][j]==dp[i][j-1]:
    j -= 1
  else:
    ans = n[i-1]+ans
    i -= 1
    j -= 1
print(ans)