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

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in range(n):
    l = lcm(l, a[i])
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)
### BUGGY CODE ###

import fractions
import functools
N = int(input())
a = list(map(int, input().split()))

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

def lcm_list(lst):
    return functools.reduce(lcm,lst)

lcma = lcm_list(a)-1
res = 0
for i in a:
    res += lcma%i
print(int(res))

### FIXED CODE ###

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

res = 0
for i in a:
    res += i-1
print(int(res))
### BUGGY CODE ###

import heapq

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

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print(sum(A))

### FIXED CODE ###


import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1], reverse=True)

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print(sum(A))
"""
import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        l = bisect.bisect_left(A, c)
        print(l)
        l = min(b, l)
        A = A[l:] + [c] * l
        print(l, A)

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

A, B, C, D = map(int,input().split())

d={}
for i in range(A,C+1):
  d[(i,B)] = B**(i-A)
for j in range(B,D+1):
  d[(A,j)] = A**(j-B)
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]
    
print(d[(C,D)] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
A = np.array(readline().split(),np.int64)
F = np.array(readline().split(),np.int64)

A.sort()
F.sort()
F=F[::-1]
 
new_list_a = np.array(A)
new_list_f = np.array(F)
 
for i in range(K):
  time = new_list_f * new_list_a
  number_a = np.argmax(time)
  new_list_a[number_a] = new_list_a[number_a] - (i - (i - 1))
  time = new_list_f * new_list_a
  
print(max(time))

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
### BUGGY CODE ###

N, X, Y = map(int, input().split())


count = [0] * (N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        routeC = abs(Y-i) + abs(X-j) + 1
        min_route = min(routeA, routeB, routeC)
        count[min_route - 1] += 1

for i in count:
    print(i)

### FIXED CODE ###

N, X, Y = map(int, input().split())


count = [0] * (N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        min_route = min(routeA, routeB)
        count[min_route - 1] += 1

print('\n'.join(map(str, count)))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    t = 0
    w = a[:i] + a[i+1:]
    w.append(0)
    w.insert(0,0)
    for h in range(len(w)-1):
        t += abs(w[h]-w[h+1])
    print(t)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.append(0)
a.insert(0,0)
s = 0
for i in range(len(a)-1):
    s += abs(a[i]-a[i+1])
for h in range(1,n+1):
    t = abs(a[h+1]-a[h-1])-abs(a[h]-a[h-1])-abs(a[h+1]-a[h])
    print(s+t)
### BUGGY CODE ###

import sys,math
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
S = list(input())

ANS = 0

for i in range(N):
    f = S[i]
    for j in ['R','G','B']:
        if j==f:
            continue
        #残りの二文字のどっちかに一致するものを探す
        for k in range(i+1,N):
            elm = S[k]
            if elm!=j:
                continue
            s = elm
            #距離
            dist = k-i
            for l in range(k+1,N):
                if S[l]!=s and S[l]!=f:
                    if dist != l-k:
                        ANS += 1
print(ANS)

### FIXED CODE ###

import sys,math
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
S = list(input())

ANS = 0
dp = [None]*N
r,g,b = 0,0,0
for i in range(N):
    elm = S[i]
    if elm=='R':
        r += 1
    elif elm=='G':
        g += 1
    else:
        b += 1
    dp[i] = [r,g,b]

TTL = dp[-1]
for i in range(N):
    f = S[i]
    for j in ['R','G','B']:
        if j==f:
            continue

        for k in range(i+1,N):
            elm = S[k]
            if elm!=j:
                continue
            for l in ['R','G','B']:
                if l==f or l==elm:
                    continue

                if l=='R':
                    d = 0
                elif l=='G':
                    d = 1
                else:
                    d = 2
                ANS += TTL[d] - dp[k][d]

                if k+k-i<N and S[k+k-i]==l:
                    ANS -= 1
print(ANS)
### BUGGY CODE ###

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

max_score = 0
for x in range(1,min(b+1, n+1)):
    score = int(a*x/b) - a*int(x/b)
    if (score > max_score):
        max_score = score
        
print(max_score)

### FIXED CODE ###

import math

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

for x in range(min(b, n), 0, -1):
    score = math.floor((a*x)/b) - math.floor(a*(x//b))
    if (score > 0):
        print(score)
        break
else:
    print(0)
### BUGGY CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
max=0
idx=0
for i in range(N-K+1):
    tmp = sum(n[i:i+K]) 
    if tmp  > max:
        max=tmp 
        idx=i

d=n[idx:idx+K]
tmp=0
for i in range(K):
    tmp += np.sum(np.arange(1,d[i]+1))/d[i]
print(tmp)

### FIXED CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=(n+1)
t=np.empty(N+1)
t[0] = 0
t[1:]=np.cumsum(n)
print(max(t[K:]-t[:-K])*0.5)
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=list(map(int, input().split()))
q=int(input())
Q=[list(map(int, input().split())) for _ in range(q)]
# print(Q)

B=dict(Counter(A))
# print(B)

sum = 0
for k in B.keys():
    sum += k*B[k]
# print(B[2])
for i in range(q):
    x=Q[i][0]
    y=Q[i][1]
    if x not in B:
        print(sum)
        continue
    else:
        v = B[x]
        if y in B:
            B[y] += v
        else:
            B[y]=v
        del B[x]
        sum = 0
        for k in B.keys():
            sum += k*B[k]
        print(sum)


### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
q=int(input())
Q=[list(map(int, input().split())) for _ in range(q)]

L=[0]*(10**5+1)
S=0
for i in range(N):
    L[A[i]]+=1
    S+=A[i]

for i in range(q):
    S+=L[Q[i][0]]*(Q[i][1]-Q[i][0])
    L[Q[i][1]]+=L[Q[i][0]]
    L[Q[i][0]]=0
    # print(L)
    print(S)
### BUGGY CODE ###

S=(input())
Q=int(input())
cnt_re=0
for i in range(Q):
    q=input().split()
    if q[0]=='1':
        cnt_re+=1
    else:
        tmp=cnt_re%2
        if ((q[1]=='1')&(tmp==0)) | ((q[1]=='2')&(tmp==1)):
            S=q[2]+S
        elif ((q[1]=='1')&(tmp==1)) | ((q[1]=='2')&(tmp==0)):
            S=S+q[2]
            
if cnt_re%2==1:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

S=(input())
Q=int(input())
cnt_re=0
s=''
for i in range(Q):
    q=list(input().split())
    if q[0]=='1':
        cnt_re+=1
    else:
        if (int(q[1])+cnt_re)%2==1:
            s=s+q[2]
        else:
            S=S+q[2]
if cnt_re%2==1:
    print(S[::-1]+s)
else:
    print(s[::-1]+S)
### BUGGY CODE ###

#EDP-D, E
import sys
from collections import defaultdict
n, W = map(int, sys.stdin.readline().split())
dp = [defaultdict(int) for _ in range(n)]
#初期設定
w, v = map(int, sys.stdin.readline().split())
dp[0][w] = v
#print(dp)

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][w] = max(dp[i-1].get(w, 0), v)
    for w1, v1 in dp[i-1].items():
        dp[i][w1] = max(dp[i][w1], v1)
        if w+w1<=W:
            dp[i][w1+w] = max(dp[i][w1+w], v1+v)

print(max(dp[-1].values()))

### FIXED CODE ###

import sys
n, limit = map(int, sys.stdin.readline().split()) 
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [dict() for i in range(n)]
#print(dp)
dp[0][L[0][1]] = L[0][0]

for i in range(1, n):
    dp[i][L[i][1]] = min(L[i][0], dp[i-1].get(L[i][1], float('inf')))
    for v, w in dp[i-1].items():
        dp[i][v] = min(dp[i-1][v], dp[i].get(v, float('inf')))
        dp[i][L[i][1] + v] = min(L[i][0] + dp[i-1][v], dp[i-1].get(L[i][1] + v, float('inf'))) 
        
ans = 0
for v, w in dp[-1].items():
    if w <=limit:
        if ans < v:
            ans = v
#print(dp)
print(ans)
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1):
        for i in range(lst[0]+lst[1]+lst[2]+1):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1-k):
        for i in range(lst[0]+lst[1]+lst[2]+1-k-j):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])
### BUGGY CODE ###

N = int(input())
B = [10 ** 9 + 1]
for i in range(N):
  A = int(input())
  flag = True
  for j in range(len(B)):
    if A > B[j]:
      B[j] = A
      flag = False
      break
  if flag:
    B.append(A)
    B.sort(reverse=True)
print(len(B) - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

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

Color = []
for a in A:
  idx = bisect.bisect_right(Color,a)
  if idx == len(Color):
    Color.append(a)
  else:
    Color[idx] = a
  #Color.sort()
  #print(Color)
print(len(Color))
### BUGGY CODE ###

from numpy import*
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,k=map(int,input().split())
    a=sorted(map(int,input().split()))
    b=sorted(map(int,input().split()),reverse=1)
    #print(a,b)
    ok=max(a)*max(b)
    ng=-1
    
    def check(a,b,mid,k):
        a=array(a)
        b=array(b)
        c=[a[k]-mid//b[k]for k,v in enumerate(a*b)if v>mid]
#        print(c)
        if sum(c)<=k:
            return 1
        else:
            return 0
            
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if check(a,b,mid,k):
            ok=mid
        else:
            ng=mid
    print(ok)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,k=map(int,input().split())
    a=sorted(map(int,input().split()))
    b=sorted(map(int,input().split()),reverse=1)
    #print(a,b)
    ok=max(a)*max(b)
    ng=-1
    
    def check(a,b,mid,k):
        if sum(a[i]-mid//b[i]for i in range(n) if a[i]*b[i]>mid)<=k:
            return 1
        else:
            return 0
            
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if check(a,b,mid,k):
            ok=mid
        else:
            ng=mid
    print(ok)

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

import sys

s =  [0] + [ord(i) for i in sys.stdin.readline()] + [0, 0]

ret = 0
i = 0

while i < len(s) :
    if s[i] == 65 and s[i+1] == 66 and s[i+2] == 67 :
        j = 0
        while s[i-j-1] == 65 :
            s[i-j+1] = 65
            j += 1
        s[i-j+1] = 66

        s[i+2] = 65
        i += 2
        ret += 1 + j
        
    else :
        i += 1

print(ret)


### FIXED CODE ###

s =  list(input())

ret = 0
i = 0
a = 0
bc = 0

while True :
    while i < len(s) and s[i] == 'A' :
        a += 1
        i += 1

    while i < len(s) - 1 and s[i:i+2] == ['B', 'C']  :
        bc += 1
        i += 2

    ret += a * bc

    bc = 0

    if i < len(s) and s[i] != 'A' :
        a = 0
        
    while i < len(s) and s[i] != 'A' :
        i += 1

    if i >= len(s) - 1 :
        break
    

print(ret)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

    if i > 0: res += rec(i-1,j,k)*i
    if j > 0: res += rec(i+1,j-1,k)*j
    if k > 0: res += rec(i,j+1,k-1)*k
    res += N
    res *= 1.0/(i+j+k)
    dp[i][j][k] = res
    return res

one = a.count(1)
two = a.count(2)
three = a.count(3)

#print(dp)
print(rec(one,two,three))
#print(dp)


### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
for x in range(A[0]+1):
    t = x
    B = [x]
    for i in range(n-1):
        B.append(A[i]-t)
        t = B[-1]
    if 2*sum(B)==sum(A):
        break
ans = [i*2 for i in B]
print(" ".join(map(str,ans)))

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
x = 0
for i in range(n):
    if i%2==0:
        x+=A[i]
    else:
        x-=A[i]
B = [x//2]
for i in range(n-1):
    B.append(A[i]-B[-1])
ans = [2*b for b in B]
print(" ".join(map(str,ans)))
### BUGGY CODE ###

# # 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
# #
# import deque
# H, W = map(int, input().rstrip().split())

# Map = []

# for i in range(H):
#     Map.append(list(input().rstrip()))

# black_list = []

# for i in range(H):
#     for j in range(W):
#         if Map[i][j] == "#":
#             black_list.append((i, j))


# def search(black_list):
#     next_nodes = []
#     for pos in black_list:
#         x, y = pos

#         for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
#             dx, dy = direction

#             if x+dx < 0 or y+dy < 0:
#                 continue

#             if x+dx >= H or y+dy >= W:
#                 continue

#             if Map[x+dx][y+dy] == "#":
#                 continue

#             Map[x+dx][y+dy] = "#"
#             next_nodes.append((x+dx, y+dy))

#     return next_nodes


# count = 0
# while black_list:
#     black_list = search(black_list)
#     if len(black_list) > 0:
#         count += 1

# print(count)

from collections import deque
H, W = map(int, input().rstrip().split())

Map = []

for i in range(H):
    Map.append(list(input().rstrip()))

black_list = []

check = [[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if Map[i][j] == "#":
            check[i][j] = 1
            black_list.append((i, j))

queue = deque(black_list)

while queue:
    pos = queue.popleft()
    x, y = pos

    # 各方向を確認する
    for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        dx, dy = direction

        if x+dx < 0:
            continue
        if x+dx >= H:
            continue
        if y+dy < 0:
            continue
        if y+dy >= W:
            continue

        # 白は黒に置き換える
        if check[x+dx][y+dy] == 0:
            check[x+dx][y+dy] = check[x][y] + 1
            queue.append((x+dx, y+dy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < check[i][j]:
            ans = check[i][j]

print(ans-1)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

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

from functools import reduce

A = int(input())
lst = [int(x) for x in input().split()]
res = reduce(lambda a, b: a * b, lst)
print(res if res <= pow(10, 18) else -1)


### FIXED CODE ###

res = 1

A = int(input())
N = sorted([int(x) for x in input().split()])

for x in N:
    res *= x
    if res > pow(10, 18):
        res = -1
        break

print(res)
### BUGGY CODE ###

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

s = set(a)

ans = 0

for x in s:
    c = a.count(x)
    if c > x:
        ans += c - x
    if c < x:
        ans += c

print(ans)


### FIXED CODE ###

import collections

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

c = collections.Counter(a)
ans = 0

for k, v in c.items():
    if k > v:
        ans += v
    if k < v:
        ans += v - k
    
print(ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
l = [list(map(int, input().split())) for _ in range(q)]
ind = []
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ind.append(i+1)

for ll in l:
    print(len([j for j in ind if ll[0] <= j < ll[1]]))

### FIXED CODE ###

N, q = map(int, input().split())
S = input()
Q = [list(map(int ,input().split())) for _ in range(q)]

cnt = [0] * (N+1)
tmp = S[0]
for i in range(2,N+1):
	if tmp == "A" and S[i-1] == "C":
		cnt[i] = cnt[i-1] + 1
	else:
		cnt[i] = cnt[i-1]

	tmp = S[i-1]

for l,r in Q:
	ans = cnt[r] - cnt[l-1]

	if S[l-2] == "A" and S[l-1] == "C":
		ans -= 1

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

s = str(input())
length = len(s)
count = 0
for i in range(length - 2):
  for j in range(i+3, length + 1):
    if int(s[i:j])%2019 == 0:
      count += 1
print(count)

### FIXED CODE ###

s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  d %= 2019
  counts[remain] += 1

ans = 0
for count in counts:
  ans += count*(count - 1) / 2
print(int(ans))