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

from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = readline().strip()[::-1]
    N = len(S)

    a = [0]
    s = 0
    for i in range(N):
        s += int(S[i]) * 10**i
        a.append(s % 2019)
    
    t = Counter(a)

    ans = 0
    for _, v in t.items():
        ans += v * (v-1) // 2
    
    print(ans)
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = [int(s) for s in list(input().strip())][::-1]
    N,P = len(S), 2019
    
    num = 0
    ans = 0
    
    if P == 2 or P == 5:
    	for i in range(N):
    		if S[i] % P == 0:
    			ans += N-i
    	print(ans)
    	return

    L = [0] * P
    L[0] = 1
    t = 0
    s = 1
	
    for z in S:
    	t = (z * s + t)%P	
    	L[t]+=1
    	s = s * 10 % P
	
    for l in L:
    	ans += l * (l - 1) // 2
    
    print(ans)


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

import numpy as np
a,b=map(int,input().split())
num=[x for x in range(a,b+1)]
p=np.prod(num)
if p>0:
    print('Positive')
elif p<0:
    print('Negative')
else:
    print('Zero')

### FIXED CODE ###

a,b=map(int,input().split())
if 0<a<=b:
    print('Positive')
elif a<=b<0:
    if (b-a+1)%2==0:
        print('Positive')
    else:
        print('Negative')
else:
    print('Zero')
### BUGGY CODE ###

def union(group, new_mem):
    if  (group[new_mem[0]-1] * group[new_mem[1]-1]) < 0: 
        choice = max(group[new_mem[0]-1], group[new_mem[1]-1])
       
        for i in range(len(new_mem)):
            group[new_mem[i]-1] = choice
            
    elif group[new_mem[0]-1] <0 and group[new_mem[1]-1] < 0:
        for i in range(len(new_mem)):
            group[new_mem[i]-1] = min(new_mem[0], new_mem[1])
        
    elif (group[new_mem[0]-1] != group[new_mem[1]-1])  and (group[new_mem[0]-1] * group[new_mem[1]-1]) > 0: 
        old = max(group[new_mem[0]-1], group[new_mem[1]-1])
        new = min(group[new_mem[0]-1], group[new_mem[1]-1])
        for i in range(len(group)):
            if group[i] == old:
                group[i] = new
                 
    return group

def find(group, v):
    return group[v-1]

def size(group, v):
    input_v = find(group, v)
    return group.count(input_v)
    
n,m = map(int, input().split())
bridge = []
for i in range(m):
    a, b= map(int, input().split())
    bridge.append((a,b))

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

group = [-i  for i in range(1, n+1)] 
tmp = total
group_before = group.copy()
for i in range(m-1,0,-1):
    group = union(group, bridge[i]) 
    
    if find(group_before,bridge[i][0]) == find(group_before, bridge[i][1]):
        non_route.append(tmp)
    else:
        n_1 = size(group_before, bridge[i][0])
        n_2 = size(group_before, bridge[i][1])
        tmp -=   n_1 * n_2
        non_route.append(tmp)
    group_before = group.copy()

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])

### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
    
n,m = map(int, input().split())
bridge = []
for i in range(m):
    a, b= map(int, input().split())
    bridge.append((a,b))

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

uft = UnionFind(n)

tmp = total

for i in range(m-1,0,-1):
    a = bridge[i][0] -1
    b = bridge[i][1] -1

    if uft.issame(a, b):
        non_route.append(non_route[-1])
        continue
    ra = uft.size(a)
    rb = uft.size(b)
    non_route.append(non_route[-1] - ra * rb)
    uft.merge(a, b)

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])
### BUGGY CODE ###

import sys
import copy
def input():
    return sys.stdin.readline()
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

for i in range(n):
  tmp = copy.copy(a)
  tmp[i] = 0
  print(max(tmp))
  #print(tmp)

### FIXED CODE ###

import sys
import copy
def input():
    return sys.stdin.readline()
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))


A = max(a)
if a.count(A) >= 2:
  for i in range(n):
    print(A)
else:
  index = a.index(A)
  for i in range(index):
    print(A)
  print(sorted(a)[-2])
  for i in range(index+1,n):
    print(A)
### BUGGY CODE ###

import re
import itertools
import copy

N, K = map(int,input().split())
S = input()
lstS = list(S)
where0 = []

pattern = r'0+'

iterator = re.finditer(pattern ,S)
for match in iterator:
    where0.append(list(map(int, match.span())))

if len(where0) <= K:
    print(N)
    exit()

kouho = list(range(len(where0)))
conbination = list(itertools.combinations(kouho,K))

maxlength = 0
for conbi in conbination:
    temp = copy.copy(lstS)
    tempstr = ''
    for i in range(len(conbi)):
        for j in range(where0[conbi[i]][0], where0[conbi[i]][1]):
            temp[j] = '1'
    for x in temp:
        tempstr += x
    cnt = 0
    for i in range(len(tempstr)):
        if temp[i] == '1':
            cnt += 1
            if cnt > maxlength:
                maxlength = cnt
        else:
            cnt = 0

print(maxlength)

### FIXED CODE ###

N, K = map(int,input().split())
S = input()
lstS = list(S)
block = [0]

cnt = 1
for i in range(len(S)):
    if S[i:i+1] == S[i+1:i+2]:
        cnt += 1
    else:
        block.append(cnt)
        cnt = 1
block.append(0)

acc = [0, 0]
for i in range(1, len(block)):
    wa = acc[-1]+block[i]
    acc.append(wa)

if S[0] == '0':
    start = 0
else:
    start = 1
end = len(acc) - (2*K+1)

max = 0
for i in range(start, end, 2):
    if max < acc[i+(2*K+1)] - acc[i]:
        max = acc[i+(2*K+1)] - acc[i]

if start >= end:
    max = N

if len(S) == 1:
    if K == 0 and S =='0':
        max = 0
    else:
        max = 1

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

N,M = map(int,input().split())
AB= []
for i in range(N):
    AB.append([int(j) for j in input().split()])

AB = sorted(AB, key=lambda x: x[0], reverse=False)
AB = sorted(AB, key=lambda x: x[1], reverse=True)

for i in range(N):  #同じ仕事があっても消せるようにIDを振る
    AB[i].append(i)

money = 0

def NdayOK(n):  #あとn日残されているときに選べる仕事のリスト
    nd = []
    for i in range(N):
        if AB[i][0] <= n:
            nd.append(AB[i])
    return(nd)

checker = []
for i in range(M+1):
    NOi = NdayOK(i)
    for j in range(len(NOi)):
        if NOi[j][2] not in checker:
            money += NOi[j][1]
            checker.append(NOi[j][2])
            break

print(money)

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
L=[[] for i in range(M+1)]

for i in range(N):
    if AB[i][0]<=M:
        L[AB[i][0]].append(-AB[i][1])

LL=[]
money=0

for i in range(1,M+1):
    for j in L[i]:
        heapq.heappush(LL,j)
    if len(LL)==0:
        continue
    money+=heapq.heappop(LL)

print(-money)
### BUGGY CODE ###

(n, m)  =map(int, input().split())

map = {}
i = 2
while m != 1:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e % 1000000007
print(sum )

### FIXED CODE ###

import math
(n, m)  =map(int, input().split())
sqm = math.sqrt(m)
map = {}
i = 2
y = m
while m != 1 and sqm >= i:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
if m > 1:
    map[m] = 1

sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e % 1000000007
print(sum )
### BUGGY CODE ###

N, M = (int(i) for i in input().split())

ans = 0
while True:
    if N >= 1 and M >= 2:
        N -= 1
        M -= 2
        ans += 1
    elif M >= 2:
        M -= 2
        N += 1
    else:
        break

print(ans)

### FIXED CODE ###

N, M = (int(i) for i in input().split())

ans = 0

if M-2*N < 0:
    ans = M // 2
else:
    ans = N + (M-2*N) // 4

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

import sys
from collections import Counter
readline = sys.stdin.buffer.readline

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

for j in range(n):
  b = 0
  for i, v in enumerate(a):
    if i != j:
      b ^= v
  print(b)

### FIXED CODE ###

import sys
from functools import reduce
from operator import xor
readline = sys.stdin.buffer.readline

n = int(readline())
a = tuple(map(int, readline().split()))

s = reduce(xor, a[1:], a[0])
# print(s)
b = tuple(str(s ^ v) for v in a)
print(' '.join(b))
### BUGGY CODE ###

import time
import itertools

N = int(input())
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

start = time.time()

p = list(itertools.product(range(1,40),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

for n in range(1,N + 1):
    print(a.count(n))

elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")


### FIXED CODE ###

import time
import itertools
import collections

N = int(input())
start = time.time()
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

p = list(itertools.product(range(1,100),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

dict = collections.Counter(a)

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

class BIT:
    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s

N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = []
for i in range(Q):
    l,r = map(int,input().split())
    LR.append((l,r,i))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = [0]*Q
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS[i] = bit.sum(r)-bit.sum(l-1)
for a in ANS:
    print(a)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = [0]*Q
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        #良い玉の情報を更新する
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    print(*ans, sep="\n")
main()
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
hope = []
for i in range(N):
  hope.append((P[i]+1)/2)

for j in range(N-K+1):
  ans = max(ans,sum(hope[j:j+K]))

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
### BUGGY CODE ###

from fractions import Fraction
from functools import reduce

n = int(input())
num = list(map(int, input().split()))
num = [ Fraction(i) for i in num ]

if 0 in num:
    print(0)
elif len([i for i in num if i >= 10**18]) != 0:
    print(-1)
else:
    mult = reduce(lambda x, y: x*y, num)
    if mult > 10**18:
        print(-1)
    else:
        print(int(mult))

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(2,int(pow(p,1/n))+2):
        x=pow(i,n)
        if x>p:
            break
        if p%x==0:
            res=i
print(res)

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  print(a.count(i + 1))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
c = dict(c)
for i in range(n):
  if i + 1 in c.keys():
    print(c[i + 1])
  else:
    print(0)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
def lcm(a,b): return abs(a * b)/gcd(a,b) if a and b else 0

n = input()

xs = [int(x) for x in input().split()]

mlcm = 1
for x in set(xs):
  mlcm = lcm(mlcm, x)

mlcm -= 1
mlcm = int(mlcm)
print(sum([ mlcm%x for x in xs]))

### FIXED CODE ###

n = input()
xs = [int(x)-1 for x in input().split()]
print(sum(xs))
### BUGGY CODE ###

from collections import deque
    
N,M,K=map(int,input().split())
A={i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)

C={i:set() for i in range(1,N+1)}
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

T={i:False for i in range(1,N+1)}
V=set([i for i in range(1,N+1)])
E=[]
p=0
while p<N:
    v=V.pop()
    S=deque([v])
    T[v]=True
    p+=1
    D=[]
    while S:
        w=S.pop()
        D.append(w)
        for u in [u for u in A[w] if not T[u]]:
            p+=1
            T[u]=True
            S.append(u)
    E.append(set(D))
    V-=set(D)

        
F=["*"]+[0]*(N)
for i in range(len(E)):
    for x in E[i]:
        F[x]=i

for i in range(1,N+1):
    c=F[i]
    print(len(E[c]-(A[i]|C[i]|{i})),end="")
    if i!=N:
        print(" ",end="")
print()


### FIXED CODE ###

class Union_Find():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

A=[set() for _ in range(N+1)]
U=Union_Find(N+1)
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)
    U.union(a,b)

C=[set() for _ in range(N+1)]
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

S=[]
for k in range(1,N+1):
    t=U.size(k)
    for a in C[k]:
        if U.find(a)==U.find(k):
            t-=1

    t-=len(A[k])
    S.append(t-1)

print(" ".join(map(str,S)))
### BUGGY CODE ###

def sr(x):
    y = ''
    for i in range(len(x)-1,-1,-1):
        y = '%s%s' %(y,x[i])
    return y

s = input()
q = int(input())

for i in range(q):
    x = input().split()
    
    if (x[0] == '1'):
        #s = s[::-1]
        s = sr(s)
    else:
        s = '%s%s'%(x[2],s) if (x[1] == '1') else '%s%s'%(s,x[2])

print(s)


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

l, r = [ int(_) for _ in input().split() ]

ls = [2018]

for i in range(l,r):
    for j in range(i+1,r+1):
        if (i*j) % 2019 < min(x%2019 for x in ls):
            ls.append(i*j)
        
print(min([ x%2019 for x in ls]))

### FIXED CODE ###

#ABC 133 Remainder Minimization 2019
l, r = [ int(_) for _ in input().split() ]

ls = [2018]

for i in range(l,r):
    for j in range(i+1,r+1):
        y = (i*j) % 2019
        if (i*j) % 2019 < min(x%2019 for x in ls):
            ls.append(i*j)
        if y == 0:
            break
    if y == 0:
        break
    
print(min([ x%2019 for x in ls]))
### BUGGY CODE ###

## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)
    
INF = 1 << 50
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw

            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] != INF:continue
            if abs(dh) + abs(dw) <= 1:
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###

N=int(input())
S=list(input())

ans=0
i=0
while i<N-2:
    j=i+1
    while j<N-1:
        k=j+1
        while k<N:
            if S[i]==S[j]:
                break
            ans+=1*(S[j]!=S[k])*(S[k]!=S[i])*(j-i!=k-j)
            k+=1
        j+=1
    i+=1

print(ans)



### FIXED CODE ###

N=int(input())
S=list(input())

ans=S.count('R')*S.count('G')*S.count('B')


i=0
while i<N-1:
    j=i+1
    while 2*j-i<N:
        ans-=1*(S[i]!=S[j])*(S[j]!=S[2*j-i])*(S[2*j-i]!=S[i])
        j+=1
    i+=1

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

s, t = sorted([input(), input()], key=lambda x: len(x))
len_s, len_t = len(s), len(t)

dp = [[""] * len_t for _ in range(2)]
index = 0
for i in range(len_s):
    index = i % 2
    sameStr = ""
    for j in range(len_t):
        aboveStr = dp[index-1][j]
        if s[i] == t[j]:
            sameStr = aboveStr + s[i]
        dp[index][j] = sameStr if len(sameStr) >= len(aboveStr) else aboveStr

print(dp[index][-1])

### FIXED CODE ###

sList, tList = list(input()), list(input())

dp = [[0] * (len(tList) + 1) for _ in range(len(sList) + 1)]
for i, s in enumerate(sList, start=1):
    sameNum = 0
    for j, t in enumerate(tList, start=1):
        num = dp[i-1][j]
        if s == t:
            sameNum = max(num, dp[i-1][j-1] + 1)
        dp[i][j] = max(num, sameNum)

ans = ""

while(i > 0, j > 0):
    num = dp[i][j]
    if num == 0:
        break
    if sList[i-1] == tList[j-1]:
        ans = sList[i-1] + ans
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

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

from sys import stdin

n = int(stdin.readline().rstrip())
data = list(stdin.readline().rstrip().split()[0])

r_list = []
g_list = []
b_list = []


for i in range(n):
    if data[i] == "R":
        r_list.append(i)
    elif data[i] == "G":
        g_list.append(i)
    else:
        b_list.append(i)

count = len(r_list) * len(g_list) * len(b_list)

for r in r_list:
    for g in g_list:
        for b in b_list:
            if abs(r-g) == abs(g-b) or abs(r-b) == abs(g-b) or abs(r-b) == abs(r-g):
                count -= 1

print(count)

### FIXED CODE ###

N = int(input())
S = input()

R_cnt, G_cnt, B_cnt = 0, 0, 0

for i in range(len(S)):
    if S[i] == "R":
        R_cnt += 1
    elif S[i] == "G":
        G_cnt += 1
    else:
        B_cnt += 1

All = R_cnt * G_cnt * B_cnt

for i in range(N-2):
    for j in range(i+1, N-1):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            All -= 1

print(All)
### BUGGY CODE ###

import math

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()

def check(x):
  k = K
  for i in range(N):
    k -= max(0,math.ceil((A[i]*F[i]-x)/F[i]))

  return k >= 0



left = 0
right = 10**12

if check(left):
  print(0)
  exit()

while left + 1 < right:
  mid = (left + right)//2
  if check(mid):
    right = mid
  else:
    left = mid


print(right)


### FIXED CODE ###

import math

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

A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort(reverse=True)
F.sort()

def check(x):
  k = K
  for i in range(N):
    k -= max(0,math.ceil((A[i]*F[i]-x)/F[i]))

  return k >= 0



left = 0
right = 10**12

if check(left):
  print(0)
  exit()

while left + 1 < right:
  mid = (left + right)//2
  if check(mid):
    right = mid
  else:
    left = mid


print(right)