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 10^5 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.

Difficulty: interview

Starter code:

Solutions:
def get_substr_ends(haystack, needle):
	ans = [-1]
	index = 0
	for char in needle:
		while index < len(haystack) and char != haystack[index]:
			index += 1
		ans.append(index)
		if index < len(haystack):
			index += 1
	return ans

haystack = input()
needle = input()

pref = get_substr_ends(haystack, needle)
suff = get_substr_ends(haystack[::-1], needle[::-1])

pref_index = 0
suff_len = 0
while suff_len < len(suff) and suff[suff_len] < len(haystack):
	suff_len += 1

suff_len -= 1
best_str = needle[len(needle) - suff_len:]

if len(best_str) == len(needle):
	print(needle)
	return

for pref_len in range(1, len(pref)):
	while suff_len >= 0 and suff[suff_len] + pref[pref_len] + 2 > len(haystack):
		suff_len -= 1
	ans = pref_len + suff_len
	if ans > len(best_str) and suff_len >= 0:
		best_str = needle[:pref_len] + needle[len(needle) - suff_len:]

print(best_str if best_str else '-')


a = input()
b = input()

x = []

j = 0
for i in range(len(a)):
	if (j >= len(b)):
		break
	if (a[i] == b[j]):
		x.append(i)
		j += 1

y = []
j = len(b) - 1
for i in range(len(a) - 1, -1, -1):
	if (j < 0):
		break
	if (a[i] == b[j]):
		y.append(len(a) - i - 1)
		j -= 1

lb, rb = 0, 0

ans = len(b)
if (ans > len(b) - len(x)):
	ans = len(b) - len(x)
	lb = len(x)
if (ans > len(b) - len(y)):
	ans = len(b) - len(y)
	lb = 0
	rb = len(y)

#ans = min(len(b) - len(x), len(b) - len(y))

j = len(y) - 1


for i in range(len(x)):
	if (i + j + 2 > len(b)):
		j -= 1
	while (j >= 0 and x[i] + y[j] + 2 > len(a)):
		j -= 1
	if (j < 0):
		break
	if (ans > len(b) - i - j - 2):
		ans = len(b) - i - j - 2
		lb = i + 1
		rb = j + 1
	#ans = min(ans, len(b) - i - j - 2)


if (ans == len(b)):
	print('-')
else:
	for i in range(lb):
		print(b[i], end = '')
	for i in range(len(b) - rb, len(b)):
		print(b[i], end = '')



a = input()
b = input()
p = [None] * (len(b) + 1)
s = [None] * (len(b) + 1)
j = 0
p[0] = -1
for i in range(len(b)):
    while j < len(a) and a[j] != b[i]:
        j += 1
    if j >= len(a):
        break
    else:
        p[i + 1] = j
        j += 1
j = len(a) - 1
s[-1] = len(b)
for i in range(len(b) - 1, -1, -1):
    while j >= 0 and a[j] != b[i]:
        j -= 1
    if j < 0:
        break
    else:
        s[i] = j
        j -= 1
ans = ""
for i in range(len(b) + 1):
    if p[i] == None:
        break
    else:
        l = i - 1
        r = len(b)
        while l + 1 < r:
            mid = (l + r) // 2
            if s[mid] != None and p[i] < s[mid]:
                r = mid
            else:
                l = mid
        if len(ans) < i + len(b) - r:
            ans = b[:i] + b[r:]
if ans == "":
    print("-")
else:
    print(ans)

import math 

def prefixIds(a, b):
	prefSubsId = [math.inf] * len(b)

	# print(a)
	# print(b)

	bId = 0
	aId = 0

	while aId < len(a):
		if bId == len(b):
			break

		if a[aId] == b[bId]:
			prefSubsId[bId] = aId + 1
			bId += 1
			aId += 1
		else:
			aId += 1

	return prefSubsId

a = input()
b = input()

# print(a)
# print(b)

n = len(b)

prefLens = prefixIds(a, b)
suffLens = prefixIds(a[::-1], b[::-1])[::-1]

# for i in range(n):
# 	if suffLens[i] != math.inf:
# 		suffLens[i] = len(a) - suffLens[i]

# print(*prefLens, sep='\t')
# print(*suffLens, sep='\t')

prefLen = 0
suffLen = 0

minCutLen = n
lBorder = -1
rBorder = n

while suffLen < n and suffLens[suffLen] == math.inf:
	suffLen += 1

curCutLen = suffLen
# print(curCutLen)
if curCutLen < minCutLen:
	minCutLen = curCutLen
	rBorder = suffLen

while prefLen < suffLen and prefLens[prefLen] != math.inf:
	while suffLen < n and prefLens[prefLen] + suffLens[suffLen] > len(a):
		# print(suffLen)
		suffLen += 1
	# print(prefLen)
	# print(suffLen)
	curCutLen = suffLen - prefLen - 1
	# print(curCutLen)
	if curCutLen < minCutLen:
		minCutLen = curCutLen
		lBorder = prefLen
		rBorder = suffLen
	prefLen += 1
	# print(prefLens[prefLen])
	# print(suffLens[suffLen])
# 	# print()

# print("pref, suff")
# print(prefLen)
# print(suffLen)

# print(minCutLen)
# print(n)
# print(lBorder)
# print(rBorder)

if minCutLen == n:
	print('-')
elif minCutLen == 0:
	print(b)
else:
	print(b[:lBorder + 1] + b[rBorder:])

# print(maxPrefLen)
# print(maxSuffLen)


a = input()
b = input()

prefix = [-1] * len(b)
postfix = [-1] * len(b)

prefix[0] = a.find(b[0])
postfix[len(b) - 1] = a.rfind(b[len(b) - 1])

for i in range(1, len(b)):
    prefix[i] = a.find(b[i], prefix[i - 1] + 1)
    if prefix[i] == -1:
        break

for i in range(len(b) - 2, -1, -1):
    postfix[i] = a.rfind(b[i], 0, postfix[i+1])
    if postfix[i] == -1:
        break

best_left = -1
best_right = len(b)

left = -1
while left + 1 < len(b) and prefix[left + 1] != -1:
    left += 1

if left > -1:
    best_left = left
    best_right = len(b)

right = len(b)
while right - 1 >= 0 and postfix[right - 1] != -1:
    right -= 1

if right < len(b) and right + 1 < best_right - best_left:
    best_left = -1
    best_right = right

left = 0
right = len(b)

while left < right and postfix[right - 1] != -1 and postfix[right - 1] > prefix[left]:
    right -= 1

while prefix[left] != -1 and left < right < len(b):
    while right < len(b) and postfix[right] <= prefix[left]:
        right += 1

    if right >= len(b):
        break

    if right - left < best_right - best_left:
        best_left = left
        best_right = right

    left += 1

    if left == right:
        right += 1

res = b[:best_left + 1] + b[best_right:]
if res == "":
    print("-")
else:
    print(res)


a, b = input(), input()
n = len(b)
def f(a, b):
    i, t = 0, [0]
    for q in a:
        if i < n and q == b[i]: i += 1
        t.append(i)
    return t
u, v = f(a, b), f(a[::-1], b[::-1])[::-1]
t = [x + y for x, y in zip(u, v)]
i = t.index(max(t))
x, y = u[i], v[i]
s = b[:x] + b[max(x, n - y):]
print(s if s else '-')

#import sys
#sys.stdin = open('in', 'r')
#n = int(input())
#a = [int(x) for x in input().split()]
#n,m = map(int, input().split())

s1 = input()
s2 = input()
l1 = len(s1)
l2 = len(s2)

dl = {}
dr = {}

i1 = 0
i2 = 0

while i1 < l1 and i2 < l2:
    while i1 < l1 and s1[i1] != s2[i2]:
        i1 += 1
    if i1 < l1:
        dl[i2] = i1
        i2 += 1
        i1 += 1

lmax = i2
if lmax == l2:
    print(s2)
else:
    i1 = l1 - 1
    i2 = l2 - 1
    while i1 >= 0 and i2 >= 0:
        while i1 >= 0 and s1[i1] != s2[i2]:
            i1 -= 1
        if i1 >= 0:
            dr[i2] = i1
            i2 -= 1
            i1 -= 1
    rmax = i2

    le = -1
    re = -1
    if l2 - lmax < rmax + 1:
        rcnt = l2 - lmax
        ls = 0
        rs = lmax
    else:
        rcnt = rmax + 1
        ls = rmax + 1
        rs = l2
    rr = rmax + 1
    for ll in range(lmax):
        while rr < l2 and (rr <= ll or dl[ll] >= dr[rr]):
            rr += 1
        if rr < l2:
            dif = rr - ll - 1
            if dif < rcnt:
                rcnt = dif
                ls = 0
                rs = ll + 1
                le = rr
                re = l2

    result = s2[ls:rs]
    if le != -1:
        result += s2[le:re]
    print(result if len(result) > 0 else '-')




import sys

s, t = input(), '*'+input()
n, m = len(s), len(t)-1
inf = 10**9

pre, suf = [-1] + [inf]*(m+1), [-1]*(m+1) + [n]

i = 0
for j in range(1, m+1):
    while i < n and s[i] != t[j]:
        i += 1
    if i == n:
        break
    pre[j] = i
    i += 1

i = n-1
for j in range(m, 0, -1):
    while 0 <= i and s[i] != t[j]:
        i -= 1
    if i == -1:
        break
    suf[j] = i
    i -= 1

max_len, best_l, best_r = 0, 0, 0
j = 1
for i in range(m+1):
    j = max(j, i+1)
    while j <= m and pre[i] >= suf[j]:
        j += 1
    if pre[i] == inf:
        break
    if max_len < i + m + 1 - j:
        max_len = i + m + 1 - j
        best_l, best_r = i, j

pre_s = t[1:best_l+1]
suf_s = t[best_r:]

print(pre_s + suf_s if max_len else '-')