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

# ?´???°?????°?????¨?????????????????°??????

import sys
import math

prim_no = {}                    # ????????°????´???°??§??????????????????????????????

def is_prime(no):
    if no == 2:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)

    max_check = int(math.sqrt(no))
    for i in range(3, max_check+1):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

def main():
    while True:
        num = sys.stdin.readline()
        if num is None or num.strip() == '':
            break

        num = int(num.strip())
        cnt = 0
        for i in range(2, num + 1):
            if is_prime(i):
                cnt += 1

        print(cnt)

if __name__ == '__main__':
    main()
    

### FIXED CODE ###

# ?´???°?????°?????¨?????????????????°??????

import sys
import math

prim_no = {2: True}                    # ????????°????´???°??§??????????????????????????????

def is_prime(no):
    if no == 2 or no == 1:
        return True
    
    if no % 2 == 0:
        return False

    if prim_no.get(no) is not None:
        return prim_no.get(no)

    max_check = int(math.sqrt(no))
    for i in range(3, max_check+1, 2):
        if no % i == 0:
            prim_no[no] = False
            return False

    prim_no[no] = True
    return True

def main():
    prim_vals = {}                         # ????????°?????§????´???°????????°
    num_data = []                          # ?????????????????????
    
    while True:
        num = sys.stdin.readline()
        if num is None or num.strip() == '':
            break

        num = int(num.strip())
        num_data.append(num)

    sorted_num_data = sorted(num_data)
    prim_num = {}
    
    for num in sorted_num_data:
        if prim_vals.get(num) is not None:
            cnt = prim_vals.get(num)
        else:
            if num == 1:
                cnt = 0
            else:
                cnt = 0

                if num % 2 == 0:
                    start_num = num -1
                else:
                    start_num = num
                    
                for i in range(start_num, 0, -2):
                    if prim_vals.get(i) is not None:
                        cnt += prim_vals.get(i)
                        break
                    
                    if is_prime(i):
                        cnt += 1
                        
                prim_vals[num] = cnt # ????????°?????§????´???°????????°????????????
        prim_num[num] = cnt

    for num in num_data:
        print(prim_num[num])

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

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

submax = 0
total = 0
for i in range(N):
    for j in range(i+1,N):
        sub = A[j]-A[i]
        if sub == submax:
            total += 1
        if sub > submax:
            total = 1
            submax = sub

print(total)


### FIXED CODE ###

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

submax = 0
amin=A[0]
total = 0
for i in range(N):
    if A[i] < amin:
        amin = A[i]
    sub = A[i]-amin
    if sub == submax:
        total += 1
    if sub > submax:
        total = 1
        submax = sub

print(total)
### BUGGY CODE ###

# coding: utf-8
N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
    B = A[:]
    B.pop(i)
    print(max(B))

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = []#value
for i in range(N):
    A.append(int(input()))
B = A[:]
B.sort()
one = B[-1]
two = B[-2]
for i in range(N):
    if A[i] == one:
        print(two)
    else:
        print(one)
### BUGGY CODE ###

import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(m.floor(A**0.5))
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

#pf = prime_factorize(fractions.gcd(A, B))
# num = 1

# for x in pf:
#     if x >= 1:
#         num = num + 1



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    if (g % i == 0):
        cnt = 0
        while g % i == 0:
            cnt = cnt + 1
            g = g // i
        primes.append([i, cnt])
    i = i + 1
    while i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 2

print(len(primes)+1)


### FIXED CODE ###

import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(m.floor(A**0.5))
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

#pf = prime_factorize(fractions.gcd(A, B))
# num = 1

# for x in pf:
#     if x >= 1:
#         num = num + 1



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    while i * i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 1
    if (g != 1):
        primes.append([g, 1])
print(len(primes)+1)
### BUGGY CODE ###

#  B
import itertools

R, G, B, N = [int(x) for x in input().split()]
RGB = [R, G, B]

cnt = 0
for i in range(N//R+1):
    g_range = (N - RGB[0]*i)//RGB[1]
    for j in range((N-R*i)//G+1):
        if R*i + G*j > N:
            continue
        rem = N - R*i - G*j
        if rem % B == 0: 
            cnt += 1
print(cnt)

### FIXED CODE ###

#  B
import itertools

R, G, B, N = [int(x) for x in input().split()]
RGB = [R, G, B]

cnt = 0
for i in range(N//R+1):
    g_range = (N - RGB[0]*i)//RGB[1]
    for j in range((N-R*i)//G+1):
        if R*i + G*j > N:
            continue
        rem = N - R*i - G*j
        if rem % B == 0: 
            cnt += 1
print(cnt)
### BUGGY CODE ###

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

flag = 1
ctn = 0
for _ in range(q):
    query = input().split()
    if flag:
        if query[0] == "1":
            flag = 0
            ctn += 1
        else:
            if query[1] == "1":
                s = query[2] + s
            elif query[1] == "2":
                s = s + query[2]
    else:
        if query[0] == "1":
            flag = 1
            ctn += 1
        else:
            if query[1] == "1":
                s = s + query[2]
            elif query[1] == "2":
                s = query[2] + s

if ctn % 2 == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque

def main():

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

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

n, t = map(int, input().split())
T = list(map(int, input().split()))

counter = 0
timer = 0
T_position = 0
for i in range(T[-1] + t):
#  print(counter, timer, T_position)
  if T[T_position] == i:
    timer = t
    if T_position != len(T) - 1:
      T_position += 1
  if timer > 0:
    counter += 1
  timer -= 1
print(counter)

### FIXED CODE ###

n, t = map(int, input().split())
T = list(map(int, input().split()))

counter = 0
for i in range(len(T) - 1):
  if T[i+1] - T[i] < t:
    counter += T[i+1] - T[i]
  else:
    counter += t
counter += t
print(counter)
### BUGGY CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

### FIXED CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])
### BUGGY CODE ###

H, W, M = map(int, input().split())

bomb = [[0 for i in range(W)] for j in range(H)]
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb[h][w] = 1
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

ans = 0
for r in r_check:
    for c in c_check:
        if bomb[r][c] == 1:
            ans = max(ans, row[r] + column[c] - 1)
        else:
            ans = max(ans, row[r] + column[c])

print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())

bomb = set()
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb.add((h, w))
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

num = len(r_check) * len(c_check)

ans = row_max + col_max - 1
flg = False
if M < num:
    ans += 1
else:
    for r in r_check:
        if flg:
            break
        for c in c_check:
            if not (r, c) in bomb:
                ans += 1
                flg = True
                break

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

a,b,n=map(int,input().split())
ans=0
for i in range(1,n+1):
    s=(a*i//b)-a*(i//b)
    if ans<s:
        ans=s
        
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n)
print((a*x)//b-a*(x//b))
### BUGGY CODE ###

n = input()
a = input().split()

for i in range( int(n) ):
    cnt = 0
    for a_i in a:
        if int(a_i) == i+1 :
            cnt += 1
    print(cnt)

### FIXED CODE ###

n = input()
a = input().split()
out = [0] * int(n)

#for i in range( int(n) ):
#    print( a.count(str(i+1)) )

for a_i in a:
    a_i = int(a_i)
    out[a_i-1] += 1

for out_i in out:
    print( out_i )
### BUGGY CODE ###

# 色々参考にしつつ

n,k,*a=map(int,open(0).read().split())
MOD=10**9+7
a.sort()
a=a[::-1]
ans=1
l=0
r=n-1
if k%2==1:
  ans=ans*a[l]
  l+=1
for i in range(k//2):
  if a[l]*a[l+1]>=a[r-1]*a[r]:
    ans=ans*(a[l]*a[l+1])
    l+=2
  else:
    ans=ans*(a[r-1]*a[r])
    r-=2
#print(ans)
if ans<0:
  ans=1
  for i in range(k):
    ans=ans*a[i]%MOD
print(ans%MOD)

### FIXED CODE ###

import sys

# after これ通る？コピペs


def solve(n, k, aaa):
    MOD = 10 ** 9 + 7

    if n == k:
        ans = 1
        for a in aaa:
            ans = ans * a % MOD
        return ans

    pos = []  # Strictly, Non-neg
    neg = []
    for a in aaa:
        if a >= 0:
            pos.append(a)
        elif a < 0:
            neg.append(a)

    if len(pos) == 0:
        if k % 2 == 1:
            neg.sort(reverse=True)
        else:
            neg.sort()
        ans = 1
        for a in neg[:k]:
            ans = ans * a % MOD
        return ans

    pos.sort()
    neg.sort(reverse=True)
    ans = 1
    r = k

    if r % 2 == 1:
        ans = ans * pos.pop() % MOD
        r -= 1

    while r > 0:
        if len(pos) <= 1:
            ans = ans * neg.pop() * neg.pop() % MOD
        elif len(neg) <= 1:
            ans = ans * pos.pop() * pos.pop() % MOD
        else:
            pm = pos[-1] * pos[-2]
            nm = neg[-1] * neg[-2]
            if pm > nm:
                ans = ans * pos.pop() * pos.pop() % MOD
            else:
                ans = ans * neg.pop() * neg.pop() % MOD
        r -= 2

    return ans


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, aaa))
### BUGGY CODE ###



n = int(input())
Dn = list(map(int, input().split()))#ダム


Mn = [0]*n
M0_max = min(Dn[0],Dn[-1])*2

for i in range(M0_max+1):
    
    Mn[0] = i
    for j in range(1,n):

        Mn[j] = 2*Dn[j-1] - Mn[j-1]
        
    valid = Mn[0] + Mn[-1] == Dn[-1]*2
    #print(i, valid)
    #print(Dn)
    #print(Mn)
    #print()

    if valid:
        print(*Mn)
        break



### FIXED CODE ###



n = int(input())
Dn = list(map(int, input().split()))#ダム


memo = 0 # M_n = M_0
for i in range(n):
    memo += Dn[i]*(-1 if i%2==0 else 1)

memo *= -1

#print(memo)



M0_max = min(Dn[0], Dn[-1])*2 
Mn0 = 0

def set_Mn0():

    for i in range(0, M0_max+1, 2):
    
        valid = i == memo 
#    print(i, memo, valid)
#    print(Dn)
#    print()

        if valid:
            Mn0 = i
            break


m0_l = 0
m0_h = M0_max
mid = m0_l + m0_h
mid = mid//2 + mid%2

while mid != memo:
    if memo < mid :
        m0_h = mid
    else:
        m0_l = mid
    
    mid = m0_l + m0_h
    mid = mid // 2 + mid%2
    
    #print(mid)

Mn0 = mid


Mn = [0]*n
Mn[0] = Mn0
for i in range(1,n):
    Mn[i] = 2*Dn[i-1]-Mn[i-1]

print(*Mn)
### BUGGY CODE ###

def C(n):
    if n < 2: return 0
    return n * (n-1) // 2    
    
n = int(input())
a = list(map(int, input().split()))
E = []

for i in range(n):
    if E.count(a[i]) == 0:
        E.append(a[i])

m = len(E)
count = 0

for i in range(m):
    num = a.count(E[i])
    count += C(num)

for i in range(n):
    l = a.count(a[i])
    print(count - C(l) + C(l-1))

### FIXED CODE ###


from collections import Counter

def C(n):
    if n < 2: return 0
    return n * (n-1) // 2    
    
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)

count = 0

for i, j in c.items():
    count += C(j)

for i in a:
    m = c[i]
    print(count - m + 1)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf') for i in range(N)]
#全ノードを取り敢えずinfにしておく
dp[0] = 0
for i in range(N-1):
    #足場を一個飛んだ時
    dp[i+1] = min(dp[i+1],dp[i] + abs(H[i+1] - H[i]))
    #足場をK個飛んだ時(2~K)
    for j in range(2,min(K+1,N-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(H[i+j]- H[i]))
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [float('inf') for i in range(N)]
#全ノードを取り敢えずinfにしておく
dp[0] = 0
for i in range(N-1):
    #足場を一個飛んだ時
    dp[i+1] = min(dp[i+1],dp[i] + abs(H[i+1] - H[i]))
    #足場をK個飛んだ時(2~K)
    for j in range(2,min(K+1,N-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(H[i+j]- H[i]))
print(dp[N-1])
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    from bisect import bisect,insort
    n=int(input())
    p=list(map(int,input().split()))
    p=[0]+p
    q=[0]*(n+1)
    for i in range(1,n+1):
        q[p[i]]=i
    lst=[0,q[n],n+1]
    ans=0
    for i in range(1,n):
        k=i
        i=n-i
        num=q[i]
        a=bisect(lst,num)
        if a==1:
            ans+=i*num*(lst[2]-lst[1])
            insort(lst,num)
        elif a==1+k:
            ans+=i*(n+1-num)*(lst[k]-lst[k-1])
            insort(lst,num)
        else:
            b=lst[a-2]
            c=lst[a-1]
            d=lst[a]
            e=lst[a+1]
            ans+=i*(d-num)*(c-b)+i*(num-c)*(e-d)
            insort(lst,num)
    print(ans)
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
f=[0]*(n+1)
for i in range(n):
    f[p[i]]=i+1
l=[0]+[i for i in range(n+1)]
r=[i+1 for i in range(n+1)]+[n+1]
ans=0
for i in range(1,n+1):
    x=f[i]
    l1,r1=l[x],r[x]
    l2,r2=l[l1],r[r1]
    ans+=i*((l1-l2)*(r1-x)+(x-l1)*(r2-r1))
    l[r1],r[l1]=l1,r1
print(ans)
### BUGGY CODE ###

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

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

ans = 0
ans += n

l1, l2 = min(n - x, x), max(n - x, x)
while True:
    if l1 == l2:
        ans += l1
        break
    else:
        ans += (l1 * 2)
        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)

print(ans)


### FIXED CODE ###

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

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

ans = 0
ans += n

l1, l2 = min(n - x, x), max(n - x, x)
#while True:
#    if l1 == l2:
#        ans += l1
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
#while True:
#    if l2 % l1 == 0:
#        ans += (l1 * ((l2 // l1) * 2 - 1))
#        break
#    else:
#        ans += (l1 * 2)
#        l1, l2 = min(l1, l2 -l1), max(l1, l2 - l1)
while True:
    if l2 % l1 == 0:
        ans += (l1 * ((l2 // l1) * 2 - 1))
        break
    else:
        ans += (l1 * 2) * (l2 // l1)
        l1, l2 = l2 % l1, l1

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

from collections import deque
s=list(input())
n=len(s)
K=int(input())
d=deque()
l=[{} for _ in range(26)]
li=[]
cnt=0
st=""

for i in range(n):
    d.append(s[i])
#print(s,len(s))
for i in range(n):
    buf=deque()
    #print(s[i])
    piv=ord(s[i])-97
    for j in range(n-i):
        v=d.popleft()
        buf.append(v)
        st="".join(buf)
        l[piv][st]=cnt
    buf.popleft()
    d=buf
#print(l)
buf=[]
for i in range(26):
    buf=list(l[i])
    if len(buf)<K:
        K=K-len(buf)
    else:
        buf.sort()
        print(buf[K-1])
        break

### FIXED CODE ###

from collections import deque
s=list(input())
K=int(input())
#max(K)=5でaaaaaはa,aa,aaa,aaaa,aaaaaの順
#よって5文字まで取れば良い
d=deque()
for i in range(len(s)):
    d.append(s[i])
comp=[]
#print(d)
for i in range(len(s)):
    buf=deque()
    for j in range(len(d)):
        v=d.popleft()
        buf.append(v)
        if j<5:
            comp.append("".join(buf))
    d=deque()
    for j in range(len(buf)):
        d.append(buf[j])
    d.popleft()
comp=list(set(comp))
comp.sort()
print(comp[K-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]
    
    def dfs(h,w,num,H,W,A,HMANY):
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H:
                dfs(h+1,w,num+1,H,W,A,HMANY)
            if w+1 <W:
                dfs(h,w+1,num+1,H,W,A,HMANY)
            if 0<=h-1:
                dfs(h-1,w,num+1, H,W,A,HMANY)
            if 0<=w-1:
                dfs(h,w-1,num+1, H,W,A,HMANY)
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                dfs(h,w,0,H,W,A,HMANY)
    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    
    # q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        
    #             q.append((h,w))
    #             A[h][w] = "."
    # ans = 0
    # while q:
    #     nextQ = deque()
    #     for h,w in q:
    #         A[h][w] = "#"
    #         if h+1 <H and A[h+1][w] == ".":
    #             nextQ.append( (h+1,w))
    #         if w+1 <W and A[h][w+1] == ".":
    #             nextQ.append((h,w+1))
    #         if 0<=h-1 and A[h-1][w] == ".":
    #             nextQ.append((h-1,w))
    #         if 0<=w-1 and A[h][w-1] == ".":
    #             nextQ.append((h,w-1))        
    #     ans += 1
    #     q = nextQ
        # num,h,w = q.popleft()        
        # if HMANY[h][w] > num and A[h][w] == ".":
        #     HMANY[h][w] = num
        #     A[h][w] = "#"
        #     if h+1 <H and A[h+1][w] == ".":
        #         q.append( (num+1,h+1,w))
        #     if w+1 <W and A[h][w+1] == ".":
        #         q.append((num+1,h,w+1))
        #     if 0<=h-1 and A[h-1][w] == ".":
        #         q.append((num+1,h-1,w))
        #     if 0<=w-1 and A[h][w-1] == ".":
        #         q.append((num+1,h,w-1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    # print(ans-1)
    print(ans)

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
exp_list = []
for i in p:
    expect = (i+1)/2
    exp_list.append(expect)
answer = 0
for j in range(n-k+1):
    ans = 0
    for l in range(j, j+k):
        ans += exp_list[l]
    answer = max(answer, ans)
print(answer)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
exp_list = []
for i in p:
    expect = (i+1)/2
    exp_list.append(expect)
s = sum(exp_list[0:k])
ans = s
for j in range(n-k):
    s -= exp_list[j]
    s += exp_list[j+k]
    if s > ans :
        ans = s
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
print(ans%1000000007)

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = (ans*i)%1000000007
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000*20000)

S = str(input())
ans = set()
check = set()

def dfs(i, j):
    if (i, j) in check:
        return
    else:
        check.add((i, j))
    if int(S[i:j+1])%2019 == 0:
        ans.add((i, j))
    if j == len(S)-1:
        return

    dfs(i+1, j+1)
    dfs(i, j+1)

if len(S) < 4:
    print(0)

else:
    dfs(0, 3)
    print(len(ans))

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])