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

N,M=map(int,input().split())
*A,=map(int,input().split())

# N本 まで使うか 10^4
dp=[0] * (N+1)

cost =[0, 2,5,5,4,5,6,3,7,6]

# 桁を追加する→最大のものに桁追加だから、問題なし
# 桁を入れ替える→無駄、初期状態では0桁しかないので単純に足す
# どの桁に追加すればよいか？二分探索をして決める。つまり、最大にしたいので逆順ソート済みにする？不要。先頭と末尾に追加で対応

for i in range(N+1):
    for a in A:
      # i > 0なら何かしら選んでないといけない
       if i + cost[a] <= N and (i == 0 or dp[i] > 0):
        new_i = i + cost[a]
        # 桁求める
        d = len(str(dp[i])) if dp[i] else 0
        tmp1 = dp[i] + (10** d) * a
        tmp2 = dp[i] * 10 + a
        tmps = [dp[new_i], tmp1, tmp2]
        m = max(tmps)
        dp[new_i] = m
        # print(new_i, tmps, m)


print(dp[N])

### FIXED CODE ###

N,M=map(int,input().split())
*A,=map(int,input().split())

# 0初期化ではダメ。組合せ不可を表し、演算しても問題ない状態にしておく
dp=[-float("inf")] * (N+1)
dp[0]=0

cost =[0, 2,5,5,4,5,6,3,7,6]
for i in range(N+1):
    for a in A:
      # -inf初期化なので、不可能なものの演算結果も同じ
       new_i = i + cost[a]
       if new_i <= N:
        dp[new_i] = max([dp[new_i],  dp[i]+1])

sa = sorted(A, reverse=True)
n = N
ans = 0
while n > 0:
  for a in sa:
    nn = n-cost[a]
    if nn >= 0 and dp[n] == dp[nn] +1:
      ans = ans * 10 + a
      n -= cost[a]
      break

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

import math


X = int(input())

p = 1
q = 1
tmp = 1

while p < math.sqrt(X):
    q = 1
    while 1:
        if p ** q > X:
            break
        else:
            if tmp < p ** q:
                tmp = p ** q
            q += 1
    p += 1

print(tmp)


### FIXED CODE ###

import math


X = int(input())

p = 2
q = 2
tmp = 4

while p < math.sqrt(X):
    q = 2
    while 1:
        if p ** q > X:
            break
        else:
            if tmp < p ** q:
                tmp = p ** q
            q += 1
    p += 1
if X > 3:
    print(tmp)
else:
    print(1)
### BUGGY CODE ###

import copy

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

B = copy.copy(A) # B=AとするだけではAを変更した時にBも変更してしまう
for i in range(N):
    A[i] = 0
    print(max(A))
    A[i] = B[i]

### FIXED CODE ###

#import copy

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

B = sorted(A, reverse=True)
m1 = B[0]
m2 = B[1]

for i in range(N):
    if A[i] == m1:
        print(m2)
    else:
        print(m1)

"""
# TLE
B = copy.copy(A) # B=AとするだけではAを変更した時にBも変更してしまう
for i in range(N):
    A[i] = 0
    print(max(A))
    A[i] = B[i]
"""
### BUGGY CODE ###

import sys

A=[0]
B=[[0,0]]
size = 0

def insert(A,B,x):
    global size,buf
    fp=B[0][0]
    try:
        i=A.index(-1)
        A[i]=[x]
        B[i]=[fp,0]
        B[fp][1]=i
        B[0][0]=i
    except:
        A.append(x)
        B.append([fp,0])
        B[fp][1]=len(B)-1
        B[0][0]=len(B)-1     
    size += 1    

def delete(A,B,x):
    global size
    p =B[0][0]
    while A[p]!=x:
        p=B[p][0]
        if p==0: return
    fp=B[p][0]
    bp=B[p][1]
    B[fp][1]=bp
    B[bp][0]=fp
    A[p]=[-1]
    B[p]=[-1,-1]
    size -= 1
    return

def deletefirst(A,B):
    global size
    if size == 0: return
    p=B[0][0]
    fp=B[p][0]
    B[0][0]=fp
    B[fp][1]=0
    A[p]=[-1]
    B[p]=[-1,-1]
    size -= 1
    return 0

def deletelast(A,B):
    global size
    if size == 0: return
    p=B[0][1]
    bp=B[p][1]
    B[0][1]=bp
    B[bp][0]=0
    A[p]=[-1]
    B[p]=[-1,-1]
    size -= 1
    return 0

n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        insert(A,B,s[1])
    elif s[0] == 'delete':
        delete(A,B,s[1])
    elif s[0] == 'deleteFirst':
        deletefirst(A,B)
    elif s[0] == 'deleteLast':
        deletelast(A,B)
    n -=1
    
e = B[0][0]
while e!=0:
    print A[e],
    e = B[e][0]

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

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

import itertools
c = itertools.combinations(p, K)
L = [sum(item) for item in c]
print(min(L))

### FIXED CODE ###

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

p.sort()
print(sum(p[:K]))
### BUGGY CODE ###

import math
import collections
import itertools

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

    MOD=10**9+7
    ans=0
    for i in range(N-1):
        for j in range(i+1,N):
                ans=ans%MOD+(A[i]*A[j])%MOD

    print(ans)

resolve()

### FIXED CODE ###

import math
import collections
import itertools

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

    B=[0]*N
    B[N-1]=A[N-1]
    MOD=10**9+7
    for j in range(N-2,0,-1):
        B[j]=(B[j+1]+A[j])%MOD
   
    ans=0
    for i in range(N-1):
        ans=ans%MOD+(A[i]*B[i+1])%MOD

    print(ans%MOD)

resolve()
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [LIST() for i in range(n)]
l = list(range(n))
ans = inf

for v in permutations(l, n):
    for i in range(n):
        for j in range(n):
            p = x[j][0] - x[i][0] 
            q = x[j][1] - x[i][1]
            cost = 1
            for k in range(1, n):
                if x[v[k-1]][0] == x[v[k]][0] - p and x[v[k-1]][1] == x[v[k]][1] - q:
                    continue
                else:
                    cost += 1
            ans = min(ans, cost)

print(ans)

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = [LIST() for i in range(n)]
reg = 0

for i in range(n):
    for j in range(n):
        if i != j:
            p = x[j][0] - x[i][0]
            q = x[j][1] - x[i][1]
            count = 0
            for k in range(n):
                for l in range(n):
                    if x[l][0] - x[k][0] == p  and x[l][1] - x[k][1] ==  q:
                        count += 1
            reg = max(reg, count)

ans = n - reg
print(ans)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    dp = [[0] * 13 for _ in range(2)]
    for i in range(len(s)):
        if s[-i-1] == "?":
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(10 ** i * j + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        else:
            if i == 0:
                dp[1][int(s[-i-1]) % 13] += 1
            else:
                for k in range(13):
                    dp[1][(10 ** i * int(s[-i-1]) + k) % 13] += (dp[0][k] % (10 ** 9 + 7))
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % (10 ** 9 + 7))


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

n = int(input())
s = [ input() for _ in range(n) ]
sl =[]
ans = 0

for i in s:
    sl.append(list(i))
    
for i in sl:
    i.sort() #sort() methodは　元を変える
    
for i in range(len(sl)-1):
    for j in range(i+1,len(sl)):
        if sl[i] == sl[j]:
            ans += 1
            
print(ans)

### FIXED CODE ###

A ={}
c = 0
for i in range(int(input())):
    a = str(sorted(input()))
    if a in A:
        A[a] += 1
        c += A[a]
    else:
        A[a] = 0
print(c)
### BUGGY CODE ###

from numpy import cumsum
from itertools import combinations
import bisect

n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]

xsort = sorted([xy[i][0] for i in range(n)])
ysort = sorted([xy[i][1] for i in range(n)])

xid = [0] * n
yid = [0] * n
l = [0] * n
cumsum_id = [[0] * n for _ in range(n)]
for i, (x, y) in enumerate(xy):
    l[i] = i
    xid[i] = bisect.bisect_left(xsort, x)
    yid[i] = bisect.bisect_left(ysort, y)
    cumsum_id[xid[i]][yid[i]] = 1
cumsum_id = cumsum(cumsum_id, axis=0)
cumsum_id = cumsum(cumsum_id, axis=1)

def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    count += cumsum_id[x1][y1]
    if x0 > 0:
        count -= cumsum_id[x0-1][y1]
        if y0 > 0:
            count += cumsum_id[x0-1][y0-1]
    if y0 > 0:
        count -= cumsum_id[x1][y0-1]
    return count

ans = 5 * 10**18
for a, b in combinations(l, 2):
    x0 = a
    x1 = b
    for c, d in combinations(l, 2):
        y0 = c
        y1 = d
        if count_points_in_rec(x0, x1, y0, y1) >= k:
            ans = min(ans, (xsort[x1]-xsort[x0]) * (ysort[y1]-ysort[y0]))

print(ans)

### FIXED CODE ###

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import copy

def gcdList(numbers):
    return reduce(gcd, numbers)
  
n = int(input())
a = list(map(int,input().split()))

max = 0

for i in range(n):
  l = copy.deepcopy(a)
  l.pop(i)
  v = gcdList(l)
  if v > max:
    max = v
    
print(max)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import copy

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

fValueList = []
lValueList = []
maxList = []

if n == 2:
  print(max(a[0], a[1]))
else:
  fValueList.append(a[0])
  lValueList.append(a[n-1])
  for i in range(1,n-1):
    g = fValueList[i-1]
    fValueList.append(gcd(g, a[i]))

  for i in range(1,n-1):
    g = lValueList[i-1]
    lValueList.append(gcd(g, a[n-1-i]))
  
  maxList.append(fValueList[n-2])
  maxList.append(lValueList[n-2])
  for k in range(n-2):
    g = gcd(fValueList[k], lValueList[n-3-k])
    maxList.append(g)
    
  print(max(maxList))
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
AB = [False]*N
for i in range(N):
    A, B = map(int, input().split())
    AB[i] = (A, -B)

AB.sort()
hq = []

ans, ct, idx = 0, 0, 0
for i in range(1, M+1):
    for j in AB[idx:]:
        A, B = j
        if A == i:
            heapq.heappush(hq, B)
            ct += 1
        else:
            idx = ct
            break
    if hq:
        B = heapq.heappop(hq)
        ans -= B
print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
W = [[] for _ in range(100005)]
for i in range(N):
    A, B = map(int, input().split())
    W[A].append(B)

hq = []

ans, ct, idx = 0, 0, 0
for A in range(1, M+1):
    for B in W[A]:
        heapq.heappush(hq, -B)
    if hq:
        B = heapq.heappop(hq)
        ans -= B
print(ans)
### BUGGY CODE ###

H, W, D = map(int, input().split())
where = [None] * (H*W+1)
for i in range(H):
    inputing = [int(i) for i in input().split()]
    for j in range(W):
        where[int(inputing[j])] = (i, j)
Q = int(input())

for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    now = l
    while now != r:
        ans += abs(where[now][0]-where[now+D][0]) + \
            abs(where[now][1]-where[now+D][1])
        now += D
    print(ans)


### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W,D=MI()
    A=LLIN(H)
    
    def get_cost(fr:tuple, to:tuple):
        return abs(fr[0]-to[0]) + abs(fr[1]-to[1])

    cord_of_x = {}
    for h in range(H):
        for w in range(W):
            cord_of_x[A[h][w]] = (h,w)

    cumsum = [0]*(H*W+1+D)
    for x in range(1,H*W):
        if x+D not in cord_of_x:
            break
        cost = get_cost(cord_of_x[x], cord_of_x[x+D])
        cumsum[x+D]+=cumsum[x]+cost


    Q=I()
    LR=LLIN(Q)
    for l,r in LR:
        d = l%D
        print(cumsum[r]-cumsum[l])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
for i in range(1, n + 1):
    ans = 0
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                p = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if p > n:
                    break
                if p == i:
                    ans += 1
    print(ans, flush=False)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10**5)]
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            p = x**2 + y**2 + z**2 + x * y + y * z + z * x
            if p <= 10**4:
                ans[p] += 1
for i in range(1, n + 1):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(N-1):
    print(A.count(i+1))
print("0")

### FIXED CODE ###

n = int(input())
 
boss_list = map(int, input().split())
 
employee_list = [0] * n
 
for boss in boss_list:
	employee_list[boss - 1] += 1
 
for employee in employee_list:
	print(employee)
### BUGGY CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)


### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
### BUGGY CODE ###

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

start = 0
end = 1
count = n
while start < n-1:
    s = lst[start]
    next_num = lst[end]
    while s + next_num == s ^ next_num:
        count += 1
        s = s + next_num
        end += 1
        if end == n:
            break
        next_num = lst[end]
    start += 1
    end = start + 1
print(count)

### FIXED CODE ###

import itertools

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

accum_xor = []
s = 0
for i in lst:
    s = s ^ i
    accum_xor.append(s)

accum_lst = list(itertools.accumulate(lst))

def bisearch(start, n, accum_xor, accum_lst):
    low = start
    high = n
    while True:
        i = (low+high)//2
        if start == 0:
            if accum_xor[i] == accum_lst[i]:
                low = i
            else:
                high = i
        else:
            if accum_xor[start-1] ^ accum_xor[i] == accum_lst[i] - accum_lst[start-1]:
                low = i
            else:
                high = i
        if high - low <= 1:
            if start == 0:
                if accum_xor[high] == accum_lst[high]:
                    flg = True
                else:
                    flg = False
            else:
                if accum_xor[start-1] ^ accum_xor[high] == accum_lst[high] - accum_lst[start-1]:
                    flg = True
                else:
                    flg = False
            break
    return high if flg else low

s = 0
for i in range(n):
    a = bisearch(i, n-1, accum_xor, accum_lst) - i + 1
    s += a
print(s)
### BUGGY CODE ###

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

b.sort(reverse=True)
c = b[a[1]:]
cnt = 0
h = 0
for i in range(len(c)):
  h = c[i]
  while True:
    h -= 1
    cnt += 1
    if h <= 0:
      break
print(cnt)

### FIXED CODE ###

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

b.sort(reverse=True)
c = b[a[1]:]
cnt = 0

for i in range(len(c)):
  cnt += c[i]

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


import math
N = int(input())

sum =0
for i in range(N):
	sum += i

print(sum)

### FIXED CODE ###


import math
N = int(input())
print(int(N * (N - 1) // 2))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
b.reverse()
c.reverse()
pat=0
for i in a:
  for j in b:
    if(j<=i):break
    br=0
    for k in range(n):
      if(c[k]<=j):
        #print(i,j,c[k],k)
        pat+=k
        br=1
        break
    if(br==0):pat+=n
print(pat)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
#print(a)
#print(b)
#print(c)
pat=0
ikeep=-1
for i in range(n):
  x=b[i]
  if(x!=ikeep):
    ikeep=x
  else:
    pat+=paty*patz
    continue
  paty=bisect.bisect_left(a,x)
  patz=n-bisect.bisect_right(c,x)
  #print(paty,patz)
  pat+=paty*patz
print(pat)
### BUGGY CODE ###

s = input()

counter = 0
for right in range(1, len(s)+1):
  for left in range(0, right):
    if int(s[left : right]) % 2019 == 0:
      counter += 1
print(counter)

### FIXED CODE ###

from collections import Counter
s = input()
ac = [0]

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * power_func(10, digit, 2019))) % 2019)
#print(ac)

C = Counter(ac)
#print(C)
ans = 0
for val in C.values():
    ans += val * (val - 1) // 2
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())

lenD = 0
D = []

it = L
while(it<=R):
    D.append(it%2019)
    lenD += 1
    if lenD>=2019*2:break
    it += 1

ans = 2019
for i in range(lenD):
    for j in range(i+1,lenD):
        a = (D[i]*D[j]) % 2019
        if ans > a:
            ans = a
            
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())

ans = 2019
it = L
while(it<=min(R,it+2019)):
    jt = it+1
    while(jt<=min(R,jt+2019)):
        a = (it*jt)%2019
        if a < ans:
            ans = a
            if ans==0:break
        jt += 1
    if ans==0:break
    it += 1
            
print(ans)
### BUGGY CODE ###

def disp(dp):
    for d in dp:
        print(d)
    print("")

s = input()
t = input()

dp = []
for i in range(len(s)+1):
    dp.append([0]*(len(t)+1))

#s のi番目 tのj番目(indexではないまでの共通部分文字列
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)
        dp[i][j] = max(dp[i][j],dp[i-1][j])
        dp[i][j] = max(dp[i][j],dp[i][j-1])

        #print(s[:i])
        #print(t[:j])
        #disp(dp)

i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    #print( "i={} j={}".format(i,j))
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i-1][j-1]+1:
        res += s[i-1]
        i -= 1
        j -= 1

print(res[::-1])

### FIXED CODE ###

S = input()
T = input()
lens = len(S)
lent = len(T)

DP = [[0]*(lent+1) for _ in range(lens+1)]

for i in range(1,lens+1):
    for j in range(1,lent+1):
        if S[i-1] == T[j-1]:
            DP[i][j] = max(DP[i][j],DP[i-1][j-1]+1)
        DP[i][j] = max(DP[i][j],DP[i][j-1])
        DP[i][j] = max(DP[i][j],DP[i-1][j])
ans = ""
i = lens
j = lent
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]
        i -= 1
        j -= 1
print(ans[::-1])