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:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 100
 
s = (raw_input())
t = (raw_input())
n=len(s)
m=len(t)
dp=[]
for i in range(n+1):
	lp=[]
	for j in range(m+1):
		lp.append(0)
	dp.append(lp)
# ans=""	
for i in range(0,n+1):
	for j in range(0,m+1):
		if(i==0 or j==0):
			continue
		if(s[i-1]==t[j-1]):
			dp[i][j]=1+dp[i-1][j-1]
			# ans=ans+s[i-1]
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
			# if(dp[i][j]==dp[i-1][j]):
			# 	ans=ans+s[i-1]
			# else:
			# 	ans=ans+t[j-1]
ii = dp[n][m]
ans=""
i=n
j=m
while(i>0 and j>0):
	if(s[i-1]==t[j-1]):
		ans=ans+s[i-1]
		i=i-1
		j=j-1
	elif(dp[i-1][j]>dp[i][j-1]):
		i=i-1
	else:	
		j=j-1	
print ans[::-1]