Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from copy import deepcopy
N, W = map(int, raw_input().split())
pre = []
V = 0
for i in range(N):
    w, v = map(int, raw_input().split())
    V += v
    pre.append((w, v))
minw = min(pre)[0]
items1 = []
items2 = []
items3 = []
items4 = []
for w, v in pre:
    if w == minw:
        items1.append((w, v))
    elif w == minw + 1:
        items2.append((w, v))
    elif w == minw + 2:
        items3.append((w, v))
    else:
        items4.append((w, v))
items1.sort(reverse=True)
items2.sort(reverse=True)
items3.sort(reverse=True)
items4.sort(reverse=True)
items = [items1, items2, items3, items4]
memo = {}

def dfs(indice, W, value):
    if W < 0:
        return -(10**9)
    if W < minw or W == 0:
        return value
    if indice in memo:
        return memo[indice]
    outOfAmmo = True
    indicel = list(indice)
    sofar = -(10**9)
    for i in range(4):
        if indice[i] < len(items[i]):
            outOfAmmo = False
            new_indice = deepcopy(indicel)
            new_indice[i] += 1
            current_item = items[i][indice[i]]
            sofar = max(sofar, dfs(tuple(new_indice), W-current_item[0], value+current_item[1]))
    memo[indice] = sofar
    if outOfAmmo:
        return value
    return sofar
print dfs((0, 0, 0, 0), W, 0)


### FIXED CODE ###

import sys
from copy import deepcopy
N, W = map(int, raw_input().split())
pre = []
V = 0
for i in range(N):
    w, v = map(int, raw_input().split())
    V += v
    pre.append((w, v))
minw = min(pre)[0]
items1 = []
items2 = []
items3 = []
items4 = []
for w, v in pre:
    if w == minw:
        items1.append((w, v))
    elif w == minw + 1:
        items2.append((w, v))
    elif w == minw + 2:
        items3.append((w, v))
    else:
        items4.append((w, v))
items1.sort(reverse=True)
items2.sort(reverse=True)
items3.sort(reverse=True)
items4.sort(reverse=True)
items = [items1, items2, items3, items4]
memo = {}

def dfs(indice, W, value):
    if W < 0:
        return -(10**9)
    if W < minw or W == 0:
        return value
    if indice in memo:
        return memo[indice]
    outOfAmmo = True
    indicel = list(indice)
    sofar = -(10**9)
    for i in range(4):
        if indice[i] < len(items[i]):
            outOfAmmo = False
            new_indice = deepcopy(indicel)
            new_indice[i] += 1
            current_item = items[i][indice[i]]
            sofar = max(sofar, dfs(tuple(new_indice), W-current_item[0], value+current_item[1]))
    memo[indice] = sofar
    if outOfAmmo:
        return value
    return sofar
print dfs((0, 0, 0, 0), W, 0)
### BUGGY CODE ###

import copy
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

for i in range(n):
    b = copy.deepcopy(a)
    b.pop(i)
    b.sort()
    print(b[-1])

### FIXED CODE ###

import copy
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
b = copy.deepcopy(a)
b.sort()
firint = b[-1]
secint = b[-2]

for i in a:
    if i == firint:
        print(secint)
    else:
        print(firint)
### BUGGY CODE ###

import bisect
N,M = map(int, input().split())
A = sorted(map(int, input().split()))
for i in range(M):
    bisect.insort(A, A.pop()//2)
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int, input().split())
A = sorted(map(int, input().split()))
for i in range(M):
    bisect.insort(A, A.pop()//2)
print(sum(A))
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
mlt = 1
for x in l:
    mlt *= x
if mlt > 10 ** 18:
    print('-1')
else:
    print(mlt)

### FIXED CODE ###

N = int(input())
l = list(map(int, input().split()))
if 0 in l:
    print(0)
    exit()
mlt = 1
for x in l:
    mlt *= x
    if mlt > 10 ** 18:
        print('-1')
        exit()
print(mlt)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=len(a)
s=0
for i in range(l):
  for j in range(l):
    if i!=j:
      if a[i]!=a[j]:
        s+=1
if s==n*(n-1):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=len(a)
m=len(set(a))

print("YES" if l==m else "NO")
### BUGGY CODE ###

N = input()                                                                                         
# c = list(map(int, input().split()))                                                               
c = input()                                                                                         
                                                                                                    
N = int(N)                                                                                          
                                                                                                    
dp = []                                                                                             
                                                                                                    
n_w = c.count('W')                                                                                  
n_r = c.count('R')                                                                                  
                                                                                                    
for i in range(N + 1):                                                                                  
    left_w = c[:i].count('W')                                                                       
    right_r = n_r - (i - left_w)                                                                         
    dp.append(max(left_w, right_r))                                                                 
                                                                                                    
print(min(dp))                                                                                      

### FIXED CODE ###

N = input()                                                                                         
c = input()                                                                                         
                                                                                                    
N = int(N)                                                                                          
                                                                                                    
n_r = c.count('R')                                                                                  
print(c[n_r:].count('R'))
### BUGGY CODE ###

x = int(input())


def func(p):
    q = 1
    while q <= x:
        q *= p
    return q / p


z = []
a = 1
y = x ** 0.5

while a <= y:
    z.append(func(a))
    a += 1

print(max(z))


### FIXED CODE ###

x = int(input())

if x == 1:
    print("1")
    exit()


def func(p):
    q = p
    while q < x:
        q *= p
        if q == x:
            return q
    if q / p == p:
        return 1
    else:
        return q // p


z = []
a = 2

while a <= x:
    z.append(func(a))
    a += 1

print(max(z))
### BUGGY CODE ###

N=int(input())

A=[int(input()) for i in range(N)]

A.sort()

ans=[A[0],A[-1]]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ans[0])
    n[1]=abs(A[l]-ans[-1])
    n[2]=abs(A[r]-ans[0])
    n[3]=abs(A[r]-ans[-1])
    if n[0]==max(n):
        ansn+=n[0]
        ans.insert(0,A[l])
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ans.insert(len(ans),A[l])
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ans.insert(0,A[r])
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ans.insert(len(ans),A[r])
        r-=1

print(ansn)

### FIXED CODE ###

N=int(input())

A=[int(input()) for i in range(N)]

A.sort()

ansl=A[0]
ansr=A[-1]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ansl)
    n[1]=abs(A[l]-ansr)
    n[2]=abs(A[r]-ansl)
    n[3]=abs(A[r]-ansr)
    if n[0]==max(n):
        ansn+=n[0]
        ansl=A[l]
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ansr=A[l]
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ansl=A[r]
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ansr=A[r]
        r-=1

print(ansn)
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        V = r * R + g * G 
        if N >= V and (N - V) % B == 0:
            cnt += 1
        else:
            continue
print(cnt)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	N = int(input())
	A = input().split()
	A = [int(s) for s in A]

	ans = -1
	for i, val in enumerate(A):
		tmp = -1
		for j, vol in enumerate(A):
			if i == j:
				continue

			if tmp == -1:
				tmp = vol
				continue

			tmp = gcd(vol, tmp)

		if ans == -1 or tmp > ans:
			ans = tmp

	print(ans)



def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
	
def main():
	N = int(input())
	A = list(map(int, input().split(" ")))
	
	L = []
	for i, val in enumerate(A):
		if i == 0:
			L.append(val)
			continue
		tmp = gcd(val, L[i-1])
		L.append(tmp)
		
	R = []
	for i, val in enumerate(reversed(A)):
		if i == 0:
			R.append(val)
			continue
		tmp = gcd(val, R[i-1])
		R.append(tmp)
		
	ans = 0
	for i, val in enumerate(A):
		if i == 0:
			tmp = R[len(A)-2]
		elif i == len(A)-1:
			tmp = L[len(A)-2]
		else:
			tmp = gcd(L[i-1], R[len(A)-i-2])
			
		if tmp > ans:
			ans = tmp
		
	print(ans)
	
def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
a=1
for i in A:
    a*=i
if a>10**18:
    print("-1")
else:
    print(a)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
prod=1
if 0 in A:
    prod=0
for i in A:
    prod*=i
    if prod>10**18:
        prod=-1
        break
print(prod)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    arr = read_h()

    cnt = 0
    for X in set(arr):
        tmp_cnt = 0
        for a in arr:
            if X - 1 <= a <= X + 1:
                tmp_cnt += 1

        cnt = max(cnt, tmp_cnt)

    print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    arr = read_h()

    from collections import Counter
    c = Counter(arr)

    cnt = 0
    for X in c.keys():
        cnt = max(cnt, c.get(X - 1, 0) + c.get(X, 0) + c.get(X + 1, 0))

    print(cnt)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())

    islands_to_1 = []
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1.append(max(boat))

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_1 in islands_to_1:
        if island_to_1 in islands_to_n:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())

    islands_to_1 = [0 for _ in range(n+1)]
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1[boat[1]] = 1

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_n in islands_to_n:
        if islands_to_1[island_to_n] == 1:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()
### BUGGY CODE ###

s = input()
n = len(s)
S=[0]*n
for i in range(n):
    if s[i]=="R":
        S[i]=1


ANS = [0] * n
tame =0
sw=1
for i in range(n):
    if S[i] == 1:
        sw=1
        tame += 1
    elif sw==1:
        t2=tame//2
        ANS[i-1] += t2+tame%2
        ANS[i] += t2
        sw=0
        tame=0
sw=1
tame=0
for i in range(n-1,-1,-1):
    if S[i] == 0:
        sw=1
        tame += 1
    elif sw==1:
        t2=tame//2
        ANS[i+1] += t2+tame%2
        ANS[i] += t2
        sw=0
        tame=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
S=[0 for i in range(n)]
for i in range(n):
    if s[i]=="R":
        S[i]=1


ANS =[0 for i in range(n)]
tame =[0,0]
k=0
for i in range(n):
    if S[i] == 1:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i-1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
tame =[0,0]
k=0
for i in range(n-1,-1,-1):
    if S[i] == 0:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i+1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)
#print(n)
### BUGGY CODE ###

from operator import mul
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
tmp = sorted(a)
M = 10**18
s = 0
ans = a[0]
for i in range(1,n):
	if 0 in a:
		print(0)
		break
	else:
		ans *= a[i]
		if ans > M:
			print(-1)
			s = 0
			break
		else:
			s = ans
if s != 0:
	print(s)
   

### FIXED CODE ###

n = int(input())
s = sorted(map(int,input().split()))
M = 10 ** 18
ans = 1
for ss in s:
	ans *= ss
	if ans > M:
		ans = -1
		break
	elif ans == 0:
		break
print(ans)
### BUGGY CODE ###

N,M,L = map(int,input().split())
abc = [[int(i) for i in input().split()] for j in range(M)]
Q = int(input())
INF = 1<<30
Path = [[INF for i in range(N)] for j in range(N)]
AnsPath = [[INF for i in range(N)] for j in range(N)]

def PathInit():
    for i in range(N):
        Path[i][i] = 0

def wasialFloid(Path):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                Path[i][j] = min(Path[i][j],Path[i][k]+Path[k][j])

PathInit()
for i,j,k in abc:
    Path[i-1][j-1] = k
    #双方向

    Path[j-1][i-1] = k
wasialFloid(Path)
for i in range(N):
    for j in range(N):
        if Path[i][j] <= L:
            AnsPath[i][j] = 1
wasialFloid(AnsPath)
for i in range(Q):
    s,t = map(int,input().split())
    if AnsPath[s-1][t-1] == INF:
        print(-1)
    else:
        print(AnsPath[s-1][t-1]-1)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

N,M,L = map(int,input().split())
abc = [[int(i) for i in input().split()] for j in range(M)]
Q = int(input())
st = [[int(i) for i in input().split()] for j in range(Q)]
INF = 1<<30
Path = [[INF for i in range(N)] for j in range(N)]
AnsPath = [[INF for i in range(N)] for j in range(N)]

def PathInit():
    for i in range(N):
        Path[i][i] = 0

PathInit()
for i,j,k in abc:
    Path[i-1][j-1] = k
    #双方向
    Path[j-1][i-1] = k

Path = floyd_warshall(Path)

for i in range(N):
    for j in range(N):
        if Path[i][j] <= L:
            AnsPath[i][j] = 1
AnsPath = floyd_warshall(AnsPath)
for s,t in st:
    if AnsPath[s-1][t-1] == INF:
        print(-1)
    else:
        print(int(AnsPath[s-1][t-1]-1))
### BUGGY CODE ###

s = input()
K = int(input())
strs = [[] for _ in range(26)]
cnts = [0]*26

for ind,i in enumerate(s):
    if(sum(cnts[:ord(i)-97])>=5):
        continue
    for j in range(1,len(s)-ind+1):
        st = s[ind:ind+j]
        if(not st in strs[ord(i)-97]):
            strs[ord(i)-97].append(st)
            cnts[ord(i)-97]+=1


cnt = 0
num = 0
while(cnt<K):
    cnt += len(strs[num])
    num += 1
num -= 1
cnt -= len(strs[num])
strs[num].sort()
print(strs[num][K-cnt-1])


### FIXED CODE ###

s = input()
K = int(input())
strs = [[] for _ in range(26)]
cnts = [0]*26

for ind,i in enumerate(s):
    if(sum(cnts[:ord(i)-97])>=5):
        continue
    for j in range(1,K+1):
        st = s[ind:ind+j]
        if(not st in strs[ord(i)-97]):
            strs[ord(i)-97].append(st)
            cnts[ord(i)-97]+=1


cnt = 0
num = 0
while(cnt<K):
    cnt += len(strs[num])
    num += 1
num -= 1
cnt -= len(strs[num])
strs[num].sort()
print(strs[num][K-cnt-1])
### BUGGY CODE ###

l,r = map(int,input().split())
ans = 2018
for i in range(l,r):
    for j in range(l+1,r+1):
        ans = min(ans,i*j%2019)
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
ans = 2018
flag = 0
for i in range(l,r):
    for j in range(l+1,r+1):
        ans = min(ans,i*j%2019)
        if ans == 0:
            flag = 1
            break
    if flag:
        break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = 10 ** 8 + 1
n, m = map(int, input().split())
state_num = 1 << n
key = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bt = 0
    for e in c:
        bt |= 1 << (e - 1)
    key.append((bt, a))

dp = [INF for _ in range(state_num)]
dp[0] = 0

for i in range(state_num):
    for j in range(m):
        ks, kc = key[j]
        state = i | ks
        cost = dp[i] + kc
        dp[state] = min(dp[state], cost)

if dp[-1] == INF:
    ans = -1
else:
    ans = dp[-1]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():

    INF = 10 ** 7
    n, m = map(int, input().split())
    state_num = 1 << n
    key = []
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bt = 0
        for e in c:
            bt |= 1 << (e - 1)
        key.append((bt, a))

    dp = [INF for _ in range(state_num)]
    dp[0] = 0

    for i in range(state_num):
        for j in range(m):
            ks, kc = key[j]
            state = i | ks
            cost = dp[i] + kc
            dp[state] = min(dp[state], cost)

    ans = dp[-1]
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M, Q = map(int, input().split())

LR_plane = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    L, R = map(int, input().split())
    LR_plane[L-1][R-1] += 1

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for j in range(p-1, q):
        for k in range(p-1, q):
            ans += LR_plane[j][k]
    print(ans)


### FIXED CODE ###

N, M, Q = map(int, input().split())

LR_plane = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    L, R = map(int, input().split())
    LR_plane[L-1][R-1] += 1

for i in range(N-1, -1, -1):
    for j in range(N+1):
        LR_plane[i][j] = LR_plane[i+1][j] + LR_plane[i][j]
        
for i in range(N+1):
    for j in range(1, N+1):
        LR_plane[i][j] = LR_plane[i][j-1] + LR_plane[i][j]

for i in range(Q):
    p, q = map(int, input().split())
    print(LR_plane[p-1][q-1])
### BUGGY CODE ###

N = int(input())
S = []
answer = []
for i in range(N):
  string = input()
  if not string in S:
    S.append(string)
print(len(S))

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  string = input()
  S.append(string)
S = sorted(S)
count = N
for i in range(N-1):
  if S[i] == S[i+1]:
    count -= 1
print(count)
### BUGGY CODE ###

import bisect
from functools import reduce

A, B, Q = map(int,input().split())
INF = float("inf")
s = [-1*INF]
t = [-1*INF]
for _ in range(A):
    s.append(int(input()))
s.append(INF)
for _ in range(B):
    t.append(int(input()))
t.append(INF)
for _ in range(Q):
    x = int(input())
    s_index = bisect.bisect_left(s,x)
    t_index = bisect.bisect_left(t,x)
    s_l = x - s[s_index-1]
    s_r = s[s_index] - x
    t_l = x - t[t_index-1]
    t_r = t[t_index] - x
    ans = reduce(min, [max(s_l,t_l), s_l + t_r*2, s_r + t_l*2, s_l*2 + t_r, s_r*2 + t_l, max(s_r,t_r)])
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
A, B, Q = map(int,input().split())
INF = 2 * 10 ** 10
S = [-INF]
T = [-INF]
for _ in range(A):
    S.append(int(input()))
S.append(INF)
for _ in range(B):
    T.append(int(input()))
T.append(INF)
for _ in range(Q):
    x = int(input())
    s = bisect_left(S, x)
    t = bisect_left(T, x)
    ans = min(max(S[s], T[t]) - x, x - min(S[s-1], T[t-1]), 2 * S[s] - T[t-1] - x, 2 * T[t] - S[s-1] - x, T[t] + x - 2 * S[s-1], S[s] + x - 2 * T[t-1])
    print(ans)
### BUGGY CODE ###

import sys


def resolve():
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline

    s = readline()
    t = readline()

    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]

    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1],
                                   dp[i + 1][j],
                                   dp[i][j + 1])

    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))


resolve()


### FIXED CODE ###

def resolve():
    import sys
    def max2(a: int, b: int):
        """
        入力された2つの整数a,bの大きいほうを返す
        Parameters
        ----------
        a, b : int
            比較したい整数
        Returns
        -------
        a or b : int
            大きいほうの整数
        """
        if a >= b:
            return a
        else:
            return b
    
    readline = sys.stdin.readline
 
    s = readline()
    t = readline()
 
    # 配るDP
    # dp[i + 1][j + 1]はsのi文字目までとtのj文字目までのLCSの長さ
    # LCS=最長共通部分列問題
    dp = [[0] * (len(t) + 1) for _ in [0] * (len(s) + 1)]
 
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i + 1][j])
            dp[i + 1][j + 1] = max2(dp[i + 1][j + 1], dp[i][j + 1])
 
    # LCSを求めたDPから部分文字列を復元
    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    print(''.join(res[::-1]))
 
 
resolve()