762_C. Two strings_28681
You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a subsequence of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.

Input

The first line contains string a, and the second line — string b. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.

Output

On the first line output a subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.

If the answer consists of zero characters, output «-» (a minus sign).

Examples

Input

hi
bob


Output

-


Input

abca
accepted


Output

ac


Input

abacaba
abcdcba


Output

abcba

Note

In the first example strings a and b don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.
from sys import stdin


def main():
    t = stdin.readline()
    s = stdin.readline()
    n = len(s) - 1
    m = len(t) - 1
    post = [-1] * n
    ss = n - 1
    st = m - 1
    while st >= 0 and ss >= 0:
        if t[st] == s[ss]:
            post[ss] = st
            ss -= 1
        st -= 1
    pre = [-1] * n
    ss = 0
    st = 0
    while st < m and ss < n:
        if t[st] == s[ss]:
            pre[ss] = st
            ss += 1
        st += 1
    low = 0
    high = n
    min_ans = n
    start = -1
    end = -1
    while low < high:
        mid = (low + high) >> 1
        ok = False
        if post[mid] != -1:
            if mid < min_ans:
                min_ans = mid
                start = 0
                end = mid - 1
                ok = True
        for i in range(1, n - mid):
            if pre[i - 1] != -1 and post[i + mid] != -1 and post[i + mid] > pre[i - 1]:
                if mid < min_ans:
                    min_ans = mid
                    start = i
                    end = i + mid - 1
                    ok = True
        if pre[n - mid - 1] != -1:
            if mid < min_ans:
                min_ans = mid
                start = n - mid
                end = n - 1
                ok = True
        if not ok:
            low = mid + 1
        else:
            high = mid
    ans = []
    for i in range(n):
        if start <= i <= end:
            continue
        ans.append(s[i])
    if min_ans == n:
        print('-')
    else:
        print(''.join(ans))


if __name__ == '__main__':
    main()

hi
bob
 abca
accepted
 abacaba
abcdcba
 edbcd
d
 aa
zzaa
 aaaaaaaaaaaa
aaa
 aaaaaabbbbbbaaaaaa
aba
 a
aaa
 ab
aba
 aaaaaaaaa
a
 njtdhyqundyedsjyvy
ypjrs
 bacb
ccacacbacbccbbccccaccccccbcbabbbaababa
 caacacaacbaa
acbbbabacacac
 asdf
gasdf
 aaaabbbbaaaa
aba
 a
zazaa
 fdtffutxkujflswyddvhusfcook
kavkhnhphcvckogqqqqhdmgwjdfenzizrebefsbuhzzwhzvc
 az
aaazazaa
 abbcc
aca
 def
abcdef
 haddack
hack
 dedcbaa
dca
 aaa
aa
 bbacaabbaaa
acaabcaa
 abxzxzxzzaba
aba
 aba
a
 abab
ab
 aaxyaba
aaba
 abacaba
aa
 asdf
fasdf
 aaaaaaaaaaaaaaaaaaaa
aaaaaaaa
 npnkmawey
areakefvowledfriyjejqnnaeqheoh
 abcabbcbcccbccbbcc
acbcaabbbbcabbbaca
 bababsbs
abs
 aa
aaab
 aa
aaaa
 aaaaabbbaaaaa
aabbaa
 abcabc
abc
 abcde
fabcde
 aaaaabbbbbbaaaaaa
aba
 abbba
aba
 bacbcaacabbaacb
cbbaaccccbcaacacaabb
 aaaab
aab
 aaaaa
aaaa
 aaaaaaaaa
aaaa
 a
b
 ac
aacacaacbaaacbbbabacaca
 c
cbcbcbbacacacbccaaccbcabaaabbaaa
 bbbbaabbababbaaaaababbaaabbbbaaabbbababbbbabaabababaabaaabbbabababbbabababaababaaaaa
bbabaaaabaaaabbaaabbbabaaabaabbbababbbbbbbbbbabbababbaababbbaaabababababbbbaaababaaaaab
 lctsczqr
qvkp
 aa
a
 abc
ksdksdsdsnabc
 a
ab
 a
aaaaaaaaa
 b
abb
 ashfaniosafapisfasipfaspfaspfaspfapsfjpasfshvcmvncxmvnxcvnmcxvnmxcnvmcvxvnxmcvxcmvh
ashish
 acbc
cacacbac
 zhbt
ztjihmhebkrztefpwty
 aaaaaaa
aaa
 aaaaaaaaaaaa
aaaaaaaaaaaa
 b
cb
 aaeojkdyuilpdvyewjfrftkpcobhcumwlaoiocbfdtvjkhgda
mlmarpivirqbxcyhyerjoxlslyfzftrylpjyouypvk
 abcd
zzhabcd
 uglyqhkpruxoakm
cixxkpaaoodpuuh
 test
t
 baababaaaab
baababbbbbbb
 a
a
 ofih
ihfsdf
 gkvubrvpbhsfiuyha
ihotmn
 abba
aba
 abcd
faaaabbbbccccdddeda
 accac
baacccbcccabaabbcacbbcccacbaabaaac
 aaa
aaaaa
 hddddddack
hackyz
 ababbbbbbbbbbbb
abbbbb
 babababbaaabb
abbab
 ccccabccbb
cbbabcc
 ba
bb
 aa
aa
 lo
euhaqdhhzlnkmqnakgwzuhurqlpmdm
 bbaabb
ab
 aac
aaa
 ddbcd
d
 aa
zyaa
 aaaaabaaa
a
 njtdhyqundyedsjyvy
ypjqs
 babb
ccacacbacbccbbccccaccccccbcbabbbaababa
 caacacaacbaa
cacacababbbca
 asdf
gatdf
 b
zazaa
 koocfsuhvddywslfjukxtufftdf
kavkhnhphcvckogqqqqhdmgwjdfenzizrebefsbuhzzwhzvc
 fed
abcdef
 eedcbaa
dca
 bbacabbbaaa
acaabcaa
 baba
ab
 aaxyaba
baaa
 fsda
fasdf
 abcabbcbcccbccbbcc
acabbbacbbbbaacbca
 bababsbs
asb
 abcde
edcbaf
 aaaabbabbbbaaaaaa
aba
 bcaabbacaacbcab
cbbaaccccbcaacacaabb
 b
b
 c
cbcbcbbacacacbccaaccccabaaabbaaa
 bbbbaabbababbaaaaababbaaabbbbaaabbbababbbbabaabababaabaaabbbabababbbabababaababaaaaa
bbabaaaabaaaabbaaabbbabaaabaabbbababbbbbbbbbbabbababbaababbbaaabababaaabbbbaaababaaaaab
 rqzcstcl
qvkp
 ashfaniosafapisfasipfaspfaspfaspfapsfjpasfshvcmvncxmvnxcvnmcxvnmxcnvmcvxvnxmcvxcmvh
asgish
 acbc
bacacbac
 zhbt
ztjihmhebjrztefpwty
 adghkjvtdfbcoioalwmuchbocpktfrfjweyvdpliuydkjoeaa
mlmarpivirqbxcyhyerjoxlslyfzftrylpjyouypvk
 mkaoxurpkhqylgu
cixxkpaaoodpuuh
 tset
t
 baabaaaabab
baababbbbbbb
 ofih
ihfsef
 aaaaaabbbbbbaaaaaa
aca
 a{
aaazazaa
 bbbcc
aca
 abxzxzxzzaba
aca
 aca
a
 abacaca
aa
 npnkeawmy
areakefvowledfriyjejqnnaeqheoh
 ba
aaaa
 aaaaa
aab
 ad
aacacaacbaaacbbbabacaca
 a
ba
 a
aaaabaaaa
 b
acb
 aaaaaaa
baa
 b
bb
 abcd
dcbahzz

- ac abcba d aa aaa aba a ab a ys ba aacacac asdf aba a kvc a ac def hack dca aa acaabaa aba a ab aaba aa asdf aaaaaaaa a acbc abs aa aa aabbaa abc abcde aba aba cbcaabb aab aaaa aaaa - a c bbbbbbbabbababbaababbbaaabababababbbbaaababaaaaab q a abc a a b ashish ac zt aaa aaaaaaaaaaaa b ouypvk abcd uh t baababb a ih ih aba a aac aaa hack abbbbb abbab cabcc b aa - ab aa d
 aa
 a
 jqs
 ba
 cacacabaa
 df
 -
 kc
 f
 dca
 acaaaa
 ab
 aaa
 fa
 acabbb
 asb
 e
 aba
 cbbacaabb
 b
 c
 bbbbbbbabbababbaababbbaaabababaaabbbbaaababaaaaab
 q
 asish
 ac
 zt
 mpvk
 uh
 t
 baababb
 ih
 aa
 a
 -
 aa
 a
 aa
 a
 a
 aa
 a
 a
 a
 b
 aa
 b
 d
