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

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
pq = [[int(_) for _ in input().split()] for _ in range(Q)]

dp = [[0 for j in range(N - i)]for i in range(N)]
for k in range(M):
    for i in range(N):
        for j in range(N - i):
            dp[i][j] += 1 if i + 1 <= LR[k][0] and LR[k][1] <= i + j + 1 else 0
for l in range(Q):
    print(dp[pq[l][0] - 1][pq[l][1] - pq[l][0]])

### FIXED CODE ###

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))

score=1
for i in range(K):
    score*=A[i]

for i in range(K,N):
    pre=score
    score//=A[i-K]
    score*=A[i]
    if score>pre:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))

score=1
for i in range(K):
    score+=A[i]

for i in range(K,N):
    pre=score
    score-=A[i-K]
    score+=A[i]
    if score>pre:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  e[l].append((r,d))
  e[r].append((l,-d))

INF = float('inf')
c = [INF for _ in range(n)]

def dfs(u,x):
  if c[u] == INF:
    c[u] = x
  else:
    if c[u] != x:
      print('No')
      exit()
  for v,d in e[u]:
    if c[v] != INF and c[v] == c[u]+d:
      continue
    dfs(v,c[u]+d)

for i in range(n):
  if c[i] == INF:
    dfs(i,0)
print('Yes')


### FIXED CODE ###

# D - People on a Line
import sys
sys.setrecursionlimit(10 ** 9)

n,m = map(int,input().split())
e = [[] for _ in range(n)]
for i in range(m):
  l,r,d = map(int,input().split())
  l -= 1
  r -= 1
  e[l].append((r,d))
  e[r].append((l,-d))

INF = float('inf')
c = [INF for _ in range(n)]

def dfs(u,x):
  c[u] = x
  for v,d in e[u]:
    if c[v] != INF:
      if c[v] == c[u]+d:
        continue
      else:
        print('No')
        exit()
    else:
      dfs(v,c[u]+d)

for i in range(n):
  if c[i] == INF:
    dfs(i,0)
print('Yes')
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

lcm_ = 1
for i in range(N):
    lcm_ = lcm(lcm_, A[i])

ans = 0
for i in range(N):
    ans += (lcm_ // A[i]) % mod

print(ans % mod)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

lcm_ = 1
for i in range(N):
    lcm_ = lcm(lcm_, A[i])

ans = 0
for i in range(N):
    ans += lcm_ // A[i]

print(ans % mod)
### BUGGY CODE ###

from collections import deque

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    a_book.append(a_book[index-1] + int(i))

b_book = [0]
for index, i in enumerate(input().split(), 1):
    b_book.append(b_book[index-1] + int(i))

search = deque()
check = {}


def search_count(v):
    search.appendleft(v)
    while search:
        v = search.popleft()

        if not v in check:
            check[v] = v[0] + v[1]

            if not (v[0] + 1, v[1]) in check:
                if v[0] + 1 <= N:
                    if a_book[v[0] + 1] + b_book[v[1]] <= K:
                        search.appendleft((v[0] + 1, v[1]))

            if not (v[0], v[1] + 1) in check:
                if v[1] + 1 <= M:
                    if a_book[v[0]] + b_book[v[1] + 1] <= K:
                        search.appendleft((v[0], v[1] + 1))


search_count((0, 0))

print(max(check.values()))


### FIXED CODE ###

from bisect import bisect_right
from time import time

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        N = index - 1
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        M = index - 1
        break

check = {}

max_books = 0

for i, a in enumerate(a_book):
    b_pos = bisect_right(b_book, K - a)

    if max_books < b_pos - 1 + i:
        max_books = b_pos - 1 + i

print(max_books)
### BUGGY CODE ###

s = list(input())
q = int(input())
 
me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            s.insert(0,t[2]) if me == 1 else s.append(t[2])
        else:#1=2
            s.append(t[2]) if me == 1 else s.insert(0,t[2])
 
if me != 1:
    s = s[::-1]
print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
 
me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            s.appendleft(t[2]) if me == 1 else s.append(t[2])
        else:#1=2
            s.append(t[2]) if me == 1 else s.appendleft(t[2])
s= list(s) 
if me != 1:
    s = s[::-1]
print(''.join(s))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
t = 0
for i in range(N):
    for j in range(N-i):
        X = 0
        for k in range(i+1):
            X += A[j+k]
        if X == 0:
            t += 1

print(t)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
t = 0
x = 0
B[0] = 1
for i in A:
    x += i
    t += B.get(x, 0)
    B[x] = B.get(x, 0) + 1

print(t)
### BUGGY CODE ###

#D
s=[i for i in input()]
q=int(input())
for i in range(q):
    t=input().split()
    if t[0]=='1':
        s.reverse()
    elif t[1]=='1':
        s.insert(0,t[2])
    else:
        s.append(t[2])
        
print(''.join(s))

### FIXED CODE ###

s=[input()]
q=int(input())
turn=True
l=""
for i in range(q):
    qq=input().split()
    if qq[0]=='1':
        turn=not turn
    else:
        if turn==bool(int(qq[1])-2):
            l+=qq[2]
        else:
            s.append(qq[2])

text=l[::-1]+"".join(s)
print(text if turn else text[::-1])
### BUGGY CODE ###

# ABC
s=input()
s=s.replace('BC','D')
is_ABC=True
ans=0
while is_ABC:
    t=s.count('AD')
    ans+=t
    s=s.replace('AD','DA')
    if t==0:
        is_ABC=False
print(ans)


### FIXED CODE ###

s=input()
s=s.replace("BC","D")
s=s.replace("B","E")
s=s.replace("C","E")
s=s.split("E")

t=[]
for ss in s:
  if len(ss)!=0:
    t.append(ss)
ans=0

for tt in t:
  d_cnt=0
  for i,ttt in enumerate(tt):
    if ttt=="D":
      ans+=i-d_cnt
      d_cnt+=1
print(ans)
### BUGGY CODE ###

def main():
    import sys

    input = sys.stdin.readline

    x, y, z, k = map(int, input().split())
    A = sorted(map(int, input().split()), reverse=True)
    B = sorted(map(int, input().split()), reverse=True)
    C = sorted(map(int, input().split()), reverse=True)

    ret = sorted(
        (a + b + c
         for p, a in enumerate(A)
         for q, b in enumerate(B)
         for r, c in enumerate(C)
         if p * q * r <= k
         ), reverse=True)[:k]

    print(*ret, sep='\n')


main()

# O(Klog^3K)
# https://img.atcoder.jp/abc123/editorial.pdf


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
def banned_count(seq):
    for i in range(N):
        count = 0
        C[A[i]] -= 1
        for j in C.values():
            if j >= 2:
                count = count + comb(j, 2, exact=True)
        print(count)
        C[A[i]] += 1
banned_count(A)

### FIXED CODE ###

from collections import Counter
from scipy.misc import comb
N = int(input())
A = input().split()
C = Counter(A)
s = sum([comb(j, 2, exact=True) for j in C.values()])
for i in range(N):
    print(s-C[A[i]]+1)
### BUGGY CODE ###

s=input()
l=len(s)
mod = 10**9+7
dp=[[0]*13 for _ in range(l+1)]

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]
        
print(dp[-1][5]%mod)

### FIXED CODE ###

def main():
  s=input()
  l=len(s)
  mod = 10**9+7
  dp=[[0]*13 for _ in range(l+1)]
  dp[0][0]=1 #初期値設定
  for i in range(l):
    if s[i]!="?":
      for k in range(13):
        dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
    else:
      for j in range(10):
        for k in range(13):
          dp[i+1][(k*10+j)%13]+=dp[i][k]%mod

  print(dp[-1][5]%mod)

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

s = input()
K = int(input())
l = ['zzzzzzzzzzzzzzz','zzzzzzzzzzzzzzz','zzzzzzzzzzzzz','zzzzzzzzzzzz','zzzzzzzzz']
N = len(s)

for i in range(N):
    for j in range(N-i):
        tmp = s[j:j+i+1]
        if tmp not in l:
            l.append(tmp)
        l.sort()
        l = l[0:5]


l.sort()
#print(l)


ans = l[K-1]
print(ans)



### FIXED CODE ###

s = input()
K = int(input())
l = ['zzzzzzzzzzzzzzz','zzzzzzzzzzzzzzz','zzzzzzzzzzzzz','zzzzzzzzzzzz','zzzzzzzzz']
N = len(s)

for i in range(K+1):
    for j in range(N-i):
        tmp = s[j:j+i+1]
        if tmp not in l:
            l.append(tmp)
        l.sort()
        l = l[0:5]


l.sort()
#print(l)


ans = l[K-1]
print(ans)
### BUGGY CODE ###

def culcSum(n:int)->int:
    ans = n * culcDivisor(n)
    #print(ans)
    return ans

def culcDivisor(n:int)->int:
    cnt = 0
    for idx in range(1, n+1):
        if n % idx == 0:
            cnt += 1

    return cnt

n :int = int(input())
ans = 0
for idx in range(1, n+1):
    ans += culcSum(idx)

print(ans)


### FIXED CODE ###

n = int(input())
s = 0
for i in range(1, n + 1):
  d = n // i
  s += d * (d + 1) // 2 * i
print(s)
### BUGGY CODE ###

from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1])
  edge[i+1].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i])
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]])
  edge[l[i+1][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]])
print(prim_heap())

### FIXED CODE ###

from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1))
  edge[i+1].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i))
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]))
  edge[l[i+1][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]))
print(prim_heap())
### BUGGY CODE ###

import copy

N = int(input())
txy = {}
for i in range(N):
    t, x, y = list(map(int, input().split(' ')))
    txy[t] = [x, y]

src_t = 0
src_x = 0
src_y = 0

success = True

for t, xy in txy.items():
    dest_t = t
    dest_x = xy[0]
    dest_y = xy[1]

    before = [[src_x, src_y]]
    after = []
    for i in range(src_t, dest_t):
        after.clear()
        for before_x, before_y in before:
            after.append([before_x + 1, before_y])
            after.append([before_x - 1, before_y])
            after.append([before_x, before_y + 1])
            after.append([before_x, before_y - 1])
        before = copy.deepcopy(after)

    if [dest_x, dest_y] in after:
        src_t = dest_t
        src_x = dest_x
        src_y = dest_y
        continue
    else:
        success = False
        break

if success:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n = int(input())

src_t = 0
src_x = 0
src_y = 0
success = True

for i in range(n):
    t, x, y = map(int, input().split(' '))
    if success == True:
        dt = t - src_t
        dist = abs(x - src_x) + abs(y - src_y)
        if dist <= dt and dist % 2 == dt % 2:
            src_t = t
            src_x = x
            src_y = y
            continue
        else:
            success = False

if success:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    tmp = 1
    for i in range(K):
        tmp *= A[i]

    for i in range(K,N):
        n = tmp * A[i] / A[i-K]
        if n > tmp:
            print('Yes')
        else:
            print('No')
        tmp = n

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    # tmp = 1
    # for i in range(K):
    #     tmp *= A[i]
    # print(tmp)

    for i in range(K,N):
        # n = tmp * A[i] / A[i-K]
        n = A[i]/A[i-K]
        if n > 1:
            print('Yes')
        else:
            print('No')

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

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[[0,0] for i in range(w)] for j in range(h)]
for i in range(h):
    k=0
    for j in range(w):
        cnt=0
        k=j
        while k<w and s[i][k]=="." and a[i][k][0]==0:
            k+=1
            cnt+=1
        for x in range(j,k):
            a[i][x][0]=cnt

for i in range(w):
    k=0
    for j in range(h):
        cnt=0
        k=j
        while k<h and s[k][i]=="." and a[k][i][1]==0:
            k+=1
            cnt+=1
        for x in range(j,k):
            a[x][i][1]=cnt
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j][0]+a[i][j][1])
print(ans-1)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
a=[[0]*w for j in range(h)]
b=[[0]*w for j in range(h)]
for i in range(h):
    k=0
    rep=0
    while k<w:
        cnt=0
        if s[i][k]==".":
            j=k
            while k<w and s[i][k]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                a[i][x]=cnt
        else:
            k+=1
for i in range(w):
    k=0
    while k<h:
        cnt=0
        if s[k][i]==".":
            j=k
            while k<h and s[k][i]==".":
                k+=1
                cnt+=1
            for x in range(j,k):
                b[x][i]=cnt
        else:
            k+=1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,a[i][j]+b[i][j])
print(ans-1)
### BUGGY CODE ###

n = int(input())

cnt = 0
kei = [] 
for _ in range(n):
    tmp = input()
    if not tmp in kei:
        cnt += 1
        kei.append(tmp)

print(cnt)

### FIXED CODE ###

n = int(input())

# TLE
#cnt = 0
#kei = [] 
#for _ in range(n):
#    tmp = input()
#    if not tmp in kei:
#        cnt += 1
#        kei.append(tmp)

s = set()
for _ in range(n):
    s.add(input())
cnt = len(s)

print(cnt)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

lg = set(s)

check = []
max_qua = 0

for i in lg:
    if(max_qua < s.count(i)):
        max_qua = s.count(i)
        check = [i]
    elif(max_qua == s.count(i)):
        check.append(i)

check = sorted(check)

for i in range(len(check)):
    print(check[i])

### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
p = collections.Counter(s)
res = sorted(p.items(), key=lambda x: x[1],reverse = True)
 
keys = []
#keys = [i for i,m in p.items() if m == p.values()]
u = max(p.values())
for i,m in res:
  if(m == u):
    keys.append(i)
  else:
    break
keys=sorted(keys)
for i in range(len(keys)):
  print(keys[i])
### BUGGY CODE ###

max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = a_ls[0]
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = []
  while a > 1:
    p = prime[a]
    if tmp_prime == [] or tmp_prime[-1] != p:
      tmp_prime.append(p)
    a = a//p
  for tp in tmp_prime:
    if not count_prime[tp]:
      count_prime[tp] = 1
    else:
      flg_pairwise = False
      break
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")

### FIXED CODE ###

max_num = 10**6 + 1
prime = [i for i in range(max_num)]
r2_num = int(max_num**(1/2))+1
for i in range(2, r2_num):
  if prime[i] == i:
    for j in range(i**2, max_num, i):
      if prime[j] == j:
        prime[j] = i
def gcd(a, b): # a >= b
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)

flg_pairwise = True
flg_setwise = False

n = int(input().rstrip())
a_ls = list(map(int, input().rstrip().split(" ")))
gcd_a = 0
primes_a = []
count_prime = [0 for i in range(max_num)]
for a in a_ls:
  gcd_a = gcd(gcd_a, a)
  if gcd_a == 1:
    flg_setwise = True
  tmp_prime = 0
  while a > 1:
    p = prime[a]
    pp = prime[p]
    if p == 0 or pp == 0:
      flg_pairwise = False
      break
    if tmp_prime != p:
      prime[tmp_prime] = 0
      tmp_prime = p
    a = a//p
  if flg_pairwise:
    prime[tmp_prime] = 0
  if flg_setwise and not flg_pairwise:
    break
if flg_pairwise:
  print("pairwise coprime")
elif flg_setwise:
  print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

S = input()
T = input()
N = len(S)
M = len(T)
dp = [[0] * (M+1) for _ in range(N+1)]
for i in range(1,N+1):
    for k in range(1,M+1):
        if S[i-1] == T[k-1]:
            dp[i][k] = dp[i-1][k-1] + 1
        else:
            dp[i][k] = max(dp[i-1][k],dp[i][k-1])
ans = ''
x = N
y = M
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]:
        x -= 1
    elif dp[x][y] == dp[x][y-1]:
        y -= 1
    else:
        x -= 1
        y -= 1
        ans += S[x]
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()
S = len(s)
T = len(t)
dp = [[0 for _ in range(T+1)] for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i] == t[j]:
            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])
ans = ''
i = S
j = 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:
        ans = s[i-1] + ans
        i -= 1
        j -= 1
print(ans)