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

from sys import stdin, gettrace
import sys
sys.setrecursionlimit(100000)
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def recursion(s1,s2,i,j,n1,n2,dp):
    if i>=n1 or j>=n2:
        return ""   
    if s1[i]==s2[j]:
        if dp[i+1][j+1]==-1:
            string=recursion(s1,s2,i+1,j+1,n1,n2,dp)
            dp[i+1][j+1]=string
        else:
            string=dp[i+1][j+1]
        return s1[i]+string
    else:
        if dp[i+1][j]==-1:
            x=recursion(s1,s2,i+1,j,n1,n2,dp)
            dp[i+1][j]=x
        else:
            x=dp[i+1][j]
        if dp[i][j+1]==-1:
            y=recursion(s1,s2,i,j+1,n1,n2,dp)
            dp[i][j+1]=y
        else:
            y=dp[i][j+1]
        if len(x)>len(y):
            return x
        else:
            return y

def main():
    s1=input()
    s2=input()
    n1,n2=len(s1),len(s2)
    dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
    for i in range(n1,-1,-1):
        for j in range(n2,-1,-1):
            if i==n1 or j==n2:
                dp[i][j]=""
            else:
                if s1[i]==s2[j]:
                    dp[i][j]=s1[i]+dp[i+1][j+1]
                else:
                    x=dp[i][j+1]
                    y=dp[i+1][j]
                    if len(x)>len(y):
                        dp[i][j]=x
                    else:
                        dp[i][j]=y
    print(dp[0][0])
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)
### BUGGY CODE ###

n,m = map(int,input().split())
g = [tuple(map(int,input().split())) for i in range(m)]
ans=0
for i in range(1,n+1):
  if all([t[0]<=i and i<=t[1] for t in g]):
    ans+=1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
l = []
r = []
for i in range(m):
  t = tuple(map(int,input().split()))
  l.append(t[0])
  r.append(t[1])
l,r=max(l),min(r)
if l<=r:
  print(abs(l-r)+1)
else:
  print(0)
### BUGGY CODE ###

import numpy as np
def main():
    S = input()
    S_list = []
    for i in range(len(S)):
        S_list.append(int(S[i]))
    S_list = np.array(S_list)
    num = 0
    for i in range(len(S_list)-3):
        sum_temp = np.sum([v * np.power(10, k) for k, v in enumerate(S_list[i:i+3][::-1])])
        #print(i, i+3, sum_temp)
        k = 0
        for j in range(i+3, len(S)):
            #print(S_list[j])
            sum_temp *= 10
            sum_temp += S_list[j]
            if sum_temp % 2019 == 0:
                num += 1
    print(num)

if __name__ == '__main__':
    main()

### FIXED CODE ###

S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

print(int(sum([i * (i-1) / 2 for i in num])))
### BUGGY CODE ###

import copy

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))
    
for n in numbers:
    numbers_2 = copy.deepcopy(numbers)
    c = copy.deepcopy(n)
    numbers_2.remove(c)
    print(max(numbers_2))

### FIXED CODE ###

N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))
    
    
aaa = max(numbers)
bbb = sorted(numbers)[-2]

for n in numbers:
    if aaa == n:
        print(bbb)
    else:
        print(aaa)
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
t_ = list(set(t))
for i in range(len(t_)):
  if t.count(t_[i]) > d.count(t_[i]):
    print("NO")
    exit()
print("YES")


### FIXED CODE ###

import collections

n = int(input())
d = list(map(int, input().split()))
m = int(input())
t = list(map(int, input().split()))
dc = collections.Counter(d)
tc = collections.Counter(t)
for i in tc:
    if tc[i] > dc[i]:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, 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 same(self, x, y):
        return self.find(x) == self.find(y)    


N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
uf = UnionFind(N)
 
ans=0
for l,a,b in edge:
    if uf.same(a,b):
        continue
    else:
        uf.union(a,b)
        ans += l
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    a,b,n = inpm()
    ans = int(a*n/b) - a*int(n/b)
    for i in range(1,n//b+1):
        if i*b<=n:
            x = int(a*(b*i-1)/b) - a*int((b*i-1)/b)
            ans = max(ans,x)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    a,b,n = map(int,input().split())
    print(int(a*min((b-1),n)/b) - a*int(min((b-1),n)/b))

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

K = int(input())
ansli=[]

for i in range(1, 10**9):
    if len(ansli)==K:
        print(ansli[K-1])
        exit()

    if 1<= i <=9:
        ansli.append(i)
        continue

    stri = str(i)
    leni = len(stri)

    for ii in range(leni-1):
        if int(stri[ii]) == int(stri[ii+1])-1 or \
            int(stri[ii]) == int(stri[ii+1]) or \
            int(stri[ii]) == int(stri[ii+1])+1:
            pass

        else:
            break

        if ii==leni-2:
            ansli.append(i)


### FIXED CODE ###

from collections import deque

K = int(input())
d = deque([1,2,3,4,5,6,7,8,9])
ansq = deque([1,2,3,4,5,6,7,8,9])

while len(ansq)<=K:
    num = d.popleft()

    if str(num)[-1] == "0":
        d.append(num*10)
        d.append(num*10+1)
        ansq.append(num*10)
        ansq.append(num*10+1)
        continue

    if str(num)[-1] == "9":
        d.append(num*10+8)
        d.append(num*10+9)
        ansq.append(num*10+8)
        ansq.append(num*10+9)
        continue

    d.append(num*10+int(str(num)[-1])-1)
    d.append(num*10+int(str(num)[-1]))
    d.append(num*10+int(str(num)[-1])+1)
    ansq.append(num*10+int(str(num)[-1])-1)
    ansq.append(num*10+int(str(num)[-1]))
    ansq.append(num*10+int(str(num)[-1])+1)
    
print(ansq[K-1])
### BUGGY CODE ###

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

for i in range(K):
    T = B + C
    N = A + C
    H = A + B
    if (T==N) and (N==H):
        break
    else:
        A = T
        B = N
        C = H

print( A-B if abs(A-B)<= 10**18 else 'Unfair')

### FIXED CODE ###

A,B,C,K = map(int,input().split())
a = (A-B)*(-1)**(K%2)
print(a if abs(a)<10**18 else "Unfair")
### BUGGY CODE ###

n = int(input())
s = list(sorted(input()) for i in range(n))
p = 0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            p += 1

print(p)

### FIXED CODE ###

n = int(input())
a = []
ans = 0
for i in range(n):
    a.append(sorted(input()))
a.sort()
flg = 0
for i in range(1,n):
    if a[flg] != a[i]:
        z = i - 1 - flg
        ans += (1 + z) * z // 2
        flg = i
z = n - 1 - flg
ans += (1 + z) * z // 2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    X, Y, Z, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = []
    for a in A:
        for b in B:
            for c in C:
                ans.append(a + b + c)

    ans_s = sorted(ans, reverse=True)

    for i in range(K):
        print(ans_s[i])


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    X, Y, Z, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = []
    for a in A:
        for b in B:
            ans.append(a + b)

    ans_s = sorted(ans, reverse=True)

    ans2 = []
    for a in ans_s[:3000]:
        for c in C:
            ans2.append(a + c)

    ans2_s = sorted(ans2, reverse=True)

    for i in range(K):
        print(ans2_s[i])


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

N=int(input())
A=list(map(int,input().split()))
L=list()
B=0
for i in range(N):
    L.append(A[i])
    B += max(L)-A[i]
print(B)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=0
Mi=A[0]

for i in range(1,N):
    if A[i] > Mi:
        Mi = A[i]
    B += Mi - A[i]
print(B)
### BUGGY CODE ###

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1%i==0 and x2%i==0:
            cf.append(i)
    return cf

a, b = map(int, input().split())
ab = cf(a, b)
del_cnt = 0
for i, ab_i in enumerate(ab):
    for j, ab_j in enumerate(ab[i+1:]):
        j = j+i+1 - del_cnt
        if ab_j%ab_i==0:
            del ab[j]
            del_cnt += 1

print(len(ab)+1)

### FIXED CODE ###

def pf(n:int):
    r = []
    while n%2==0:
        r.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            r.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        r.append(n)
    return r

a, b = map(int, input().split())
a = pf(a)
b = pf(b)
a = set(a)
b = set(b)
print(len(set(a&b))+1)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

res = [] 
for a in A:
    if len(res) == 0:
        res.append(a)
        res.sort()
    else:
        if a <= res[0]:
            # 小さいので追加
            res = [a] + res
        else:
            # 入れ替え
            p = bisect.bisect_left(res, a)
            res[p-1] = a
print(len(res))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            if res[p] == a:
                p = bisect(res, a-1, lambda x, y: x > y)
                res[p] = a
            else:
                res[p] = a

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

memo = [[[-1] * 201 for j in range(201)] for i in range(201)]

def gcd(numbers):
    numbers.sort()
    a = numbers[1]
    b = numbers[0]
    ans = b
    while True:
        q, mod = divmod(a, b)
        if mod == 0:
            break
        a = b
        b = mod
        ans = mod
    return ans

K = int(input())
numbers = []

for i in range(K, 0, -1):
    for j in range(i, 0, -1):
        for k in range(j, 0, -1):
            numbers.append([i, j, k])

gcd_sum = 0
for number in numbers:
    dup = len(set(number))
    a, b, c = number
    if memo[a][b][c] == -1:
        if dup == 1:
            ans = gcd([gcd([a, b]), c])
        elif dup == 2:
            ans = gcd([gcd([a, b]), c]) * 3
        else:
            ans = gcd([gcd([a, b]), c]) * 6
        memo[a][b][c] = ans
    gcd_sum += memo[a][b][c]

print(gcd_sum)


### FIXED CODE ###

memo = [[[-1] * 201 for j in range(201)] for i in range(201)]

def gcd(numbers):
    numbers.sort()
    a = numbers[1]
    b = numbers[0]
    ans = b
    while True:
        q, mod = divmod(a, b)
        if mod == 0:
            break
        a = b
        b = mod
        ans = mod
    return ans

K = int(input())
numbers = []

for i in range(K, 0, -1):
    for j in range(i, 0, -1):
        for k in range(j, 0, -1):
            numbers.append([i, j, k])

gcd_sum = 0
for number in numbers:
    dup = len(set(number))
    a, b, c = number
    if memo[a][b][c] == -1:
        if dup == 1:
            ans = gcd([gcd([a, b]), c])
        elif dup == 2:
            ans = gcd([gcd([a, b]), c]) * 3
        else:
            ans = gcd([gcd([a, b]), c]) * 6
        memo[a][b][c] = ans
    gcd_sum += memo[a][b][c]

print(gcd_sum)
### BUGGY CODE ###

N, K, L = map(int, input().split())
A = []
B = []
ans = [1 for i in range(N)]
for i in range(K):
    X = set(int(x) for x in input().split())
    for j in range(len(A)):
        if len(A[j] & X) != 0:
            A[j] = A[j] | X
            break
    else:
        A.append(X)
for i in range(L):
    Y = set(int(y) for y in input().split())
    for j in range(len(B)):
        if len(B[j] & Y) != 0:
            B[j] = B[j] | Y
            break
    else:
        B.append(Y)
for a in A:
    for b in B:
        if len(a & b) != 0:
            n = len(a & b)
            for i in a & b:
                ans[i-1] = n
print(*ans)

### FIXED CODE ###

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

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split()))
ans = 0

same = N // 2
count = 0

for i in range(2, 10 ** 5 + 1):
    count += d.count(i - 1)
    if count == same:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
d = sorted(list(map(int, input().split())))

half = d[N // 2 - 1]
nxt = d[N // 2]

if nxt == half:
    print(0)
else:
    print(nxt - (half + 1) + 1)
### BUGGY CODE ###

#!/usr/bin/env python3
#AGC37 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
h = []
for i,v in enumerate(b):
    heappush(h,(-v,i))
ans = 0
while h:
    v,i = heappop(h)
    v = -v
    tmp = b[(i+1) % n] + b[i-1]
    if v == a[i]:
        continue
    s = (v - a[i])//tmp

    if s <= 0:
        print(-1)
        quit()

    ans += s
    v -= s*tmp
    b[i] = v
    if v != a[i]:
        heappush(h,(-v,i))
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#AGC37 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
h = []
V = [0]*n
for i,v in enumerate(b):
    heappush(h,(-v,i))
    V[i] = v
ans = 0
while h:
    v,i = heappop(h)
    v = -v
    tmp = V[(i+1) % n] + V[i-1]
    if v == a[i]:
        continue
    s = (v - a[i])//tmp

    if s <= 0:
        print(-1)
        quit()

    ans += s
    v -= s*tmp
    V[i] = v
    if v != a[i]:
        heappush(h,(-v,i))
print(ans)
### BUGGY CODE ###

import bisect

N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=list(map(int,input().split()))
B=sorted(B)
C=list(map(int,input().split()))
C=sorted(C)
count=0
for num in (A):
    a=bisect.bisect_right(B,num)
    for i in range(a,len(B)):
        K=B[i]
        l=bisect.bisect_right(C,K)
        count+=len(C)-l

print(count)

### FIXED CODE ###

import bisect

N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=list(map(int,input().split()))
B=sorted(B)
C=list(map(int,input().split()))
C=sorted(C)
count=0
for num in (B):
    a=bisect.bisect_left(A,num)
    b=bisect.bisect_right(C,num)
    count+=a*(N-b)

print(count)
### BUGGY CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
for i,x in enumerate(M):
    M = [mini] + [x for x in M[1:] if x % mini != 0]
            
while len(M) > 1:
    if 1 in M:
        mini=1
        break
    M = list(map(lambda x:x-mini,M))
    M[0] = mini
    M.sort()
    while M[0]<1:
        M.pop(0)
    mini = min(mini,M[0])
print(mini)    


### FIXED CODE ###

N = int(input())
An = [int(n) for n in input().split()]
M = sorted(set(An))
mini=M[0]
            
while len(M) > 1:
    M = [mini] + [x%mini for x in M[1:] if x % mini != 0]
    M.sort()
    if 1 in M:
        mini=1
        break
    mini = min(mini,M[0])
print(M[0])
### BUGGY CODE ###

import collections
s = input()
lst = []
for i in range(len(s)):
  n = int(s[i::])
  lst.append(n%2019)
lst.append(0)

ans = 0
for i in range(2018):
  m = lst.count(i)
  ans += m*(m-1)//2
print(ans)

### FIXED CODE ###

import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * (10 ** idx) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * pow(10, idx, 2019) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()