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

# encoding: utf-8
N, K = map(int, input().split())

ans = 0

# 2 * (a + b + c) = K * (p + q + r)
for pqr in range(3, (6 * N) // K + 1):
    # a + b + c = ?
    if (pqr * K) % 2: continue
    else: abc = (pqr * K) // 2
    for p in range(max((1, -((N - abc) // K))), abc // K + 1):
        qr = pqr - p
        min_r = -((p * K - 2 * abc) // (2 * K))
        max_r = min(((2 * abc) // K - 2 * p, (abc - 1) // K))
        # count w/o r loop
        if min_r > max_r: continue
        # print(abc, (p, qr - min_r, min_r), (p, qr - max_r, max_r))
        ans += (max_r - min_r + 1) * 6
        if p == qr - min_r == min_r: ans -= 5 # p = q = r
        if p < qr - min_r == min_r: ans -= 3 # p < q = r
        if p == qr - max_r < max_r: ans -= 3 # p = q < r
            
    
print(ans)


### FIXED CODE ###

# encoding: utf-8
N, K = map(int, input().split())

ans = 0
for a in range(1, N + 1):
    # find a (a, b, c)
    # maybe TLE
    # for b in range(1, N + 1):
    #     if (a + b) % K == 0: break
    # for c in range(1, K + 1):
    #     # c and c + K returns same result
    #     if (b + c) % K == 0 and (a + c) % K == 0: break
    #     else: continue
    # else:
    #     continue # next a
    if (K - 2 * a) % K: continue
    b = K - (a % K)
    c = K - b            
    # b_min, c_min
    b_min = K - (K - b) % K
    c_min = K - (K - c) % K
    # b_max, c_max
    b_max = N - (N - b_min) % K
    c_max = N - (N - c_min) % K
    # add
    # print(a, b, c, (b_min, b_max), (c_min, c_max))
    ans += ((b_max - b_min) // K + 1) * ((c_max - c_min) // K + 1)

print(ans)
### BUGGY CODE ###

a, b, k = map(int, input().split())
ab = [i for i in range(a, b+1)]
if (b-a)//2 < k:
    ans = ab
else:
    ans = ab[0:k] + ab[len(ab)-k:len(ab)]
print(*ans)

### FIXED CODE ###

a, b, k = map(int, input().split())
if (b-a)//2 < k:
    ans = [i for i in range(a, b+1)]
else:
    ans = [i for i in range(a, a+k)] + [i for i in range(b-k+1, b+1)]
print(*ans)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)

for b,c in BC:
    for _ in range(b):
        a=heappop(A)
        if a>=c:
            heappush(A,a)
            break;
        else:
            heappush(A,c)

print(sum(A))

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
BC.sort(key=lambda x:-x[1])

D=[]
for b,c in BC:
    D.extend([c]*b)
    if len(D)>=n:
        break
D=D[:n]


for d in D:
    a=heappop(A)
    if a>=d:
        heappush(A,a)
        break;
    else:
        heappush(A,d)

print(sum(A))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def solve(li, n, s, total, cnt):
    for i in li:
        value = i * n + total
        if value > s:
            break
        if n > 1:
            a = li[:]
            a.remove(i)
            solve(a, n - 1, s, value, cnt)
        elif value == s:
            cnt[0] += 1

for line in stdin:
    n, s = (int(s) for s in line.split())

    cnt = [0]
    solve(list(range(10)), n, s, 0, cnt)
    print(cnt[0])

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def solve(li, n, s, total, cnt):
    for i in li:
        value = i * n + total
        if value > s:
            break
        if n - 1:
            subli = li[:]
            subli.remove(i)
            r = range(n - 1, 0, -1)
            minimum = value + sum(i * j for i, j in zip(r, subli))
            maximum = value + sum(i * j for i, j in zip(r, subli[::-1]))
            if minimum <= s <= maximum: 
                solve(subli, n - 1, s, value, cnt)
        elif value == s:
            cnt[0] += 1
            break

cnt = [0]
for line in stdin:
    n, s = (int(s) for s in line.split())
    cnt[0] = 0

    solve(list(range(10)), n, s, 0, cnt)
    print(cnt[0])
### BUGGY CODE ###

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]

dp = [0]*(N+1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,N+1):
    if i in a:
        continue
    dp[i] = dp[i-2] + dp[i-1]
    dp[i] = dp[i] % (10**9+7)

print(dp[N])


### FIXED CODE ###

N,M = map(int,input().split())
a = [int(input()) for i in range(M)]

dp = [-float("inf")]*(N+1)
dp[0] = 1
dp[1] = 1

for i in a:
    dp[i] = 0

for i in range(2,N+1):
    if dp[i] == 0:
        continue
    dp[i] = dp[i-2] + dp[i-1]
    dp[i] = dp[i] % (10**9+7)

print(dp[N])
### BUGGY CODE ###

N=int(input())

clear_flag=0
for i in range(N):
  txy=list(map(int,input().split()))
  x=0
  y=0
  next_flag=0
  for x_plus in range(txy[0]+1):
    if next_flag==1:
      break
    for x_minus in range(txy[0]+1-x_plus):
      if next_flag==1:
        break
      for y_plus in range(txy[0]+1-x_plus-x_minus):
        y_minus=txy[0]-x_plus-x_minus-y_plus
        x=x_plus-x_minus
        y=y_plus-y_minus
        if x==txy[1] and y==txy[2]:
          next_flag=1
          clear_flag+=1
          break
            
if clear_flag==N:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())

clear_flag=0
for i in range(N):
  txy=list(map(int,input().split()))
  if txy[0]>=(txy[1]+txy[2]) and (txy[0]+txy[1]+txy[2])%2==0:
    clear_flag+=1
  else:
    break
    
if clear_flag==N:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import math

def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
a_reverse = a[::-1]

plus = 0
minus = 0
cnt = 0
ind = 0
ceil = nCr(n, k)
while cnt < ceil:
    kaisu = nCr(n-(ind+1), k-1)
    cnt += kaisu
    plus = plus + kaisu * a_reverse[ind]
    minus = minus + kaisu * a[ind]
    ind += 1

print((plus-minus) % mod)

### FIXED CODE ###

n,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
a_reverse = a[::-1]
mod = 10**9+7
 
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod - 2, mod))
 
def comb(n, r, mod):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod

plus = 0
minus = 0
cnt = 0
ind = 0
for i in range(n-k+1):
    kaisu = comb(n-i-1, k-1, mod)
    plus = (plus + (kaisu * a_reverse[ind]) % mod) % mod
    minus = (minus + (kaisu * a[ind]) % mod) % mod
    ind += 1

print((plus-minus) % mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))

G=[[0]*(N+1) for _ in range(N+1)]
for el in uvw:
    G[el[0]][el[1]]=el[2]
    G[el[1]][el[0]] = el[2]
#print(G)

H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append(el[1])
    H[el[1]].append(el[0])
#print(H)

seen=[False]*(N+1)
distance=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt] == False:
            distance[nxt] = distance[n] + G[n][nxt]
            dfs(nxt)

dfs(1)
#print(distance)
#print(seen)

for val in distance[1:]:
    if val % 2 == 0:
        print(0)
    else:
        print(1)




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
uvw = []
for _ in range(N-1):
    uvw.append(tuple(map(int, input().split())))


H=[[] for _ in range(N+1)]
for el in uvw:
    H[el[0]].append((el[1], el[2]))
    H[el[1]].append((el[0], el[2]))
#print(H)

seen=[False]*(N+1)
color=[0]*(N+1)
def dfs(n):
    seen[n]=True
    for nxt in H[n]:
        if seen[nxt[0]] == False:
            if nxt[1] % 2 == 0:
                color[nxt[0]]=color[n]
            else:
                color[nxt[0]]=color[n] ^ 1
            dfs(nxt[0])

dfs(1)
#print(distance)
#print(seen)

for i in range(1,N+1):
    print(color[i])
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))

ab = list(itertools.permutations(a[1:]))
abc = [[0]*(n+1) for _ in range(len(ab))]

ans = 'No'

for i in range(len(ab)):
  abc[i] = list(ab[i])
  abc[i].append(a[0])
  abc[i].append(a[1])

  for j in range(1,n):
    if bin(abc[i][j-1]^abc[i][j+1]) != bin(abc[i][j]):
      break
    if j == n-1:
      ans = 'Yes'

    
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))

sa = set(a)
sa = list(sa)

if len(sa)>3:
    print('No')
    exit()

if len(sa)==3:
    aa = sa[0]
    bb = sa[1]
    cc = sa[2]
    if a.count(aa) != n/3 or a.count(bb) != n/3 or a.count(cc) != n/3:
        print('No')
        exit()
    if aa^bb^cc!=0:
        print('No')
        exit()

if len(sa)==2:
    aa = sa[0]
    bb = sa[1]
    if bb != 0 and aa != 0:
        print('No')
        exit()
    else:
        if aa==0:
            aa = bb
    if a.count(0) != n/3 or a.count(aa)!=n/3*2:
        print('No')
        exit()

if len(sa)==1:
    aa = sa[0]
    if aa != 0:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

import sys

a, b, c, d, e, f = map(int, input().split())

water_pattern = []
for i in range(f+1):
    for j in range(f+1):
        x = a*i*100 + b*j*100
        if x <= f and not x in water_pattern:
            water_pattern.append(x)

sugar_pattern = []
for i in range(f+1):
    for j in range(f+1):
        y = c*i + d*j
        if y <= f and not y in sugar_pattern:
            sugar_pattern.append(y)

sugarwater_max = -1
sugar_max = -1
concentration = 0
for i in range(len(water_pattern)):
    for j in range(len(sugar_pattern)):
        if i == 0 and j == 0:
            continue
        else:
            sugarwater = water_pattern[i] + sugar_pattern[j]
            if (water_pattern[i]/100) * e >= sugar_pattern[j] and sugarwater <= f:
                if sugarwater_max == -1 and sugar_max == -1:
                    sugarwater_max = sugarwater
                    sugar_max = sugar_pattern[j]
                    concentration = 100 * sugar_pattern[j] / sugarwater
                else:
                    if concentration < 100 * sugar_pattern[j] / sugarwater:
                        sugarwater_max = sugarwater
                        sugar_max = sugar_pattern[j]
                        concentration = 100 * sugar_pattern[j] / sugarwater

print("{} {}".format(sugarwater_max, sugar_max))

### FIXED CODE ###

# ABC074C - Sugar Water
# input
a, b, c, d, e, f = list(map(int, input().rstrip().split()))
A = a * 100
B = b * 100

# default values
x, y = min(a, b) * 100, 0  # density could be 0%
dens = y / x


# exhaustive search
for i in range(f // A + 1):
    for j in range(((f - A * i) // B) + 1):
        if i == 0 and j == 0:
            continue
        water = i * A + j * B
        rest = f - water
        for k in range(rest // c + 1):
            for l in range((rest - c * k) // d + 1):
                sugar = c * k + d * l
                total = water + sugar

                if sugar / total > e / (e + 100):  # compare to e (the max density)
                    break
                else:
                    if sugar / total > dens:
                        dens = sugar / total
                        x, y = total, sugar
print(x, y)
### BUGGY CODE ###

import math
from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n, a, b = map(int, input().split(' '))
s = 0
for i in range(1, n+1):
    if i == a or i == b:
        continue
    s += cmb(n, n-i)
print(int(s % (math.pow(10, 9)+7)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
def cmb(n, k, p):
    x, y = 1, 1
    for i in range(k):
        x = x * (n-i) % p
        y = y * (k-i) % p
    return x * pow(y, p-2, p) % p
def main():
    n, a, b = map(int, input().split())
    p = 10 ** 9 + 7
    ans = pow(2, n, p) - 1
    ans -= cmb(n, a, p) + cmb(n, b, p)
    print(ans%p)
if __name__ == "__main__":
    main()
### BUGGY CODE ###


s = input()
q = int(input())
ht = 1
count = 0
for i in range(q):
    txt3 = input().split()
    if txt3[0] == '1':
        ht = 3 - ht
        count += 1
    else:
        if int(txt3[1]) == ht:
            s = txt3[2] + s
        else:
            s = s + txt3[2]
if count % 2 == 1:
    s = s[::-1]
print(s)


### FIXED CODE ###


s = input()
q = int(input())
ht = 1
head = ''
tail = ''
count = 0
for i in range(q):
    txt3 = input().split()
    if txt3[0] == '1':
        ht = 3 - ht
        count += 1
    else:
        if int(txt3[1]) == ht:
            head = txt3[2] + head
        else:
            tail = tail + txt3[2]
s = head + s + tail
if count % 2 == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import math
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    MAX = max(A)
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            A[i] = 0
            Ms[i] = max(A)
            A[i] = MAX
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    A = deque([int(input()) for i in range(N)])
    MAX = max(A)
    MAX2 = 0
    Ms = [-1]*N
    for i in range(N):
        if A[i] == MAX:
            if MAX2 != 0:
                Ms[i] = MAX2
            else:
                A[i] = 0
                MAX2 = max(A)
                Ms[i] = MAX2
        else:
            Ms[i] = MAX
    for i in range(N):
        print(Ms[i])

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

N,M = map(int,input().split(' '))
ans = 1
for i in range(M//N):
    ans = M//N - i

    if (M - ans * N)%ans == 0:
        break
print(ans)

### FIXED CODE ###

import math


def divisor(num):
    if num < 0:
        return [0,]
    elif num == 1:
        return [1,]
    else:
        divisor_list =[1,]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i== 0:
                divisor_list.append(i)
        return divisor_list


N,M = map(int,input().split(' '))
P = M // N
divisor_list = divisor(M)

for i in reversed(range(len(divisor_list))):
    num = M // divisor_list[i]
    divisor_list.append(num)

for i in reversed(range(len(divisor_list))):
    if divisor_list[i] <= P:
        print(divisor_list[i])
        break
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="male":
    start=0
elif who=="female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="male":
        temp=0
    elif who=="female":
        temp=1
    else:
        exit()
    
    if (N%2)^start==temp:
        low=mid
    else:
        high=mid
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="Male":
    start=0
elif who=="Female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="Male":
        temp=0
    elif who=="Female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid
### BUGGY CODE ###

N, P = map(int,input().split())
 
output=1
 
for num in range(2,round(P**(1/N))+1):
  for i in range(100):
    if P%(num**N) == 0:
      P = P/(num**N)
      output = num*output
    else:
      break
 
print(output)

### FIXED CODE ###

N, P = map(int,input().split())
 
output=1
 
if P==1:
  output=1
elif N==1:
  output=P
else:
  for num in range(2,round(P**(1/N))+1):
    if P%(num**N) == 0:
      output = num
 
print(output)
### BUGGY CODE ###

from operator import mul
from functools import reduce
import itertools

N = int(input())

# N = i*jをみつける
# (i, j)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

prime_list = prime_factorize(N)


#print(prime_list)


import copy
if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12

for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = map(list, tmp)
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        #print(_, temp_origin_list)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)
print(result)

### FIXED CODE ###

import math
N = int(input())
result = N
for i in range(1, int(math.sqrt(N))+2):
    if N % i == 0:
        result = min(result, i - 1 + N//i - 1)
print(result)
### BUGGY CODE ###

n,m,*t=map(int,open(0).read().split())
d=[0,0]+[1e18]*n
for l,r,c in sorted(zip(*[iter(t)]*3)):
 for i in range(r,l,-1):d[i]=min(d[i],d[l]+c)
print(-(d[-2]>1e17)or d[-2])

### FIXED CODE ###

from heapq import*
n,_,*t=map(int,open(0).read().split())
e=[[]for _ in'_'*n]
for l,r,c in zip(*[iter(t)]*3):e[l-1]+=(c,r-1),
for i in range(n-1):e[i+1]+=(0,i),
d=[0]+[1e18]*n
q=[(0,0)]
while q:
  c,v=heappop(q)
  for b,w in e[v]:
    if b+c<d[w]:
      d[w]=b+c
      heappush(q,(b+c,w))
print(-(d[-2]>1e17)or d[-2])
### BUGGY CODE ###

def searchstar(i,j):
    global vector
    global star
    global n
    flag = False
    for k in range(n):
        if star[i][0] + vector[j][0] == star[k][0] and star[i][1] + vector[j][1] == star[k][1]:
            flag = True
            break
    return flag

while True:
    m = int(input())
    if m==0: break

    vector = []

    x1,y1 = map(int, input().split())
    for i in range(m-1):
        x2,y2 = map(int, input().split())
        vector.append([x2-x1,y2-y1])

    star = []
    n = int(input())
    for i in range(n):
        a,b = map(int, input().split())
        star.append([a,b])

    for i in range(n):
        for j in range(m-1):
            if not searchstar(i, j):
                break
        else:
            print(star[i][0] - x1, star[i][1] - y1)

### FIXED CODE ###

def searchstar(i,j):
    global vector
    global star
    global n
    flag = False
    for k in range(n):
        if star[i][0] + vector[j][0] == star[k][0] and star[i][1] + vector[j][1] == star[k][1]:
            flag = True
            break
    return flag

while True:
    m = int(input())
    if m==0: break

    vector = []

    x1,y1 = map(int, input().split())
    for i in range(m-1):
        x2,y2 = map(int, input().split())
        vector.append([x2-x1,y2-y1])

    star = []
    n = int(input())
    for i in range(n):
        a,b = map(int, input().split())
        star.append([a,b])

    for i in range(n-1,-1,-1):
        for j in range(m-1):
            if not searchstar(i, j):
                break
        else:
            print(star[i][0] - x1, star[i][1] - y1)
            break
### BUGGY CODE ###

def count_ac(string):
    return string.replace("AC", "Z").count("Z")

n, q = list(map(int, input().split(" ")))
s = input()
for _ in range(q):
    l, r = list(map(int, input().split(" ")))
    print(count_ac(s[l-1: r]))


### FIXED CODE ###

n, q = list(map(int, input().split(" ")))
s = input()
s = s.replace("AC", "ZC")
num = 0
ac_index = []
for _s in s:
    if _s == "Z":
        ac_index.append(num)
        num += 1
    else:
        ac_index.append(num)
i = 0

for _ in range(q):
    l, r = list(map(int, input().split(" ")))
    print(ac_index[r-1] - ac_index[l-1])
### BUGGY CODE ###

def resolve():
    s = input()
    t = input()

    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

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

    res = ''
    i = len(s)
    j = 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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
    
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    t = input()

    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

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

    res = ''
    i = len(s)
    j = 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
        elif dp[i][j] == dp[i - 1][j - 1] + 1:
            res = s[i - 1] + res
            i -= 1
            j -= 1

    print(res)
resolve()