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:
def main():
    s = input()
    t = input()
    dp = [["" for _ in range(3010)] for _ in range(3010)]
    for i in range(len(s)):
        for j in range(len(t)):
            dp[i + 1][j + 1] = dp[i][j + 1] if len(dp[i][j + 1]) >= len(dp[i + 1][j]) else dp[i + 1][j]
            if s[i] == t[j] and len(dp[i][j]) + 1 > len(dp[i + 1][j + 1]):
                dp[i + 1][j + 1] = dp[i][j] + s[i]
    print(dp[len(s)][len(t)])


if __name__ == '__main__':
    main()