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:
"Template made by : https://codeforces.com/profile/c1729 , github repo : https://github.com/cheran-senthil/PyRival"
from __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def main():
    s=input()
    t=input()
    L=[ [0]*(len(t)+1) for _ in range(len(s)+1) ]
    
    def lcs(s,t):
        n=len(s)
        m=len(t)
        for i in range(0,n+1):
            for j in range(0,m+1):
                if i==0 or j==0:
                    L[i][j]=0
                elif s[i-1]==t[j-1]:
                    L[i][j]=L[i-1][j-1]+1
                else :
                    L[i][j]=max(L[i-1][j],L[i][j-1])
    lcs(s,t)
    ans=[]
    i=len(s)
    j=len(t)
    while L[i][j]!=0:
        if L[i][j]!=L[i-1][j] and L[i][j]!=L[i][j-1]:
            ans.append(s[i-1])
            i-=1
            j-=1
        else :
            if L[i][j]==L[i-1][j]:
                i-=1
                continue
            else :
                j-=1
                continue
    print(''.join(ans[::-1]))
if __name__ == '__main__':
    sync_with_stdio(False)
    main()