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

#!/usr/bin/env python3
import sys
import heapq
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    heapq.heapify(A)

    for b, c in zip(B, C):
        for i in range(b):
            v = heapq.heappop(A)
            if v < c:
                heapq.heappush(A, c)
            else:
                heapq.heappush(A, v)
                break
    return sum(A)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq
import bisect
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    ret = sum(A)
    cs = Counter(A)
    for c in C:
        if c not in cs:
            cs[c] = 0
    vs = sorted(cs.keys())

    i = 0
    while cs[vs[i]] == 0:
        i += 1

    for b, c in zip(B, C):
        while 0 < b:
            if c <= vs[i]:
                break
            bb = min(b, cs[vs[i]])
            b -= bb
            cs[vs[i]] -= bb
            cs[c] += bb
            ret += bb * (c - vs[i])
            if cs[vs[i]] == 0:
                i += 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    result = solve(N, M, A, B, C)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

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

# abc152
n = int(input())
lists = list(input().split())
num_list = list(map(int,lists))
ans = 0
for i in range(n):
    if min(num_list[:i+1]) == num_list[i]:
        ans += 1
print(ans)

### FIXED CODE ###

# abc152

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

std = lists[0]
ans = 1

for i in range(1,n):
    if lists[i] < std:
        ans += 1
        std = lists[i]
        
print(ans)
### BUGGY CODE ###

import math
n = int(input())
for i in range(n):
    ans = 0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,int(math.sqrt(n))):
            for z in range(1,int(math.sqrt(n))):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i+1:
                    ans += 1
    print(ans)

### FIXED CODE ###

import math
n = int(input())
ans = [0 for _ in range(10001)]

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            t = x**2 + y**2 + z**2 + x*y + y*z + z*x 
            if t <= 10000:
                ans[t] += 1
for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
#print(N, A)
x = []
y = []
for i in range(N -1):
    amin = min(A)
    A.remove(min(A))
    amax = max(A)
    A.remove(max(A))
    #print(A, amin, amax)
    if i != N - 2:
        amin2 = abs(min(A))
        amax2 = abs(max(A))
        #print(amax2, amin2)
        if len(A) == 1:
            if A[0] < 0:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
            else:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
        else:
            if amax2 > amin2:
                A.append(amin - amax)
                x.append(amin)
                y.append(amax)
            else:
                A.append(amax - amin)
                x.append(amax)
                y.append(amin)
    else:
        A.append(amax - amin)
        x.append(amax)
        y.append(amin)

    #print("A", A)

print(A[0])
#print(x, y)
for i in range(N - 1):
    print(x[i], y[i])

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
A.sort()
A2 = collections.deque(A)
#print(N, A)
x = [0] * (N-1)
y = [0] * (N-1)
for i in range(N -1):
    amin = A2.popleft()
    amax = A2.pop()
    mainasuflag = 0
    plusflag = 0
    if i != N - 2:
        if A2[0] > 0:
            mainasuflag = 1
        if A2[len(A2) - 1] < 0:
            plusflag = 1
        amin2 = abs(A2[0])
        amax2 = abs(A2[len(A2) -1])
        if i == N - 3:
            if A2[0] > 0:
                A2.appendleft(amin - amax)
                x[i] = amin
                y[i] = amax
            else:
                A2.append(amax - amin)
                x[i] = amax
                y[i] = amin
        else:
            if mainasuflag == 1:
                A2.appendleft(amin - amax)
                x[i] = amin
                y[i] = amax
            elif plusflag == 1:
                A2.append(amax - amin)
                x[i] = amax
                y[i] = amin
            else:
                if amax2 >= amin2:
                    A2.appendleft(amin - amax)
                    x[i] = amin
                    y[i] = amax
                else:
                    A2.append(amax - amin)
                    x[i] = amax
                    y[i] = amin

    else:
        A2.append(amax - amin)
        x[i] = amax
        y[i] = amin

    #print("A", A2, mainasuflag, plusflag)

print(A2[0])
#print(x, y)
for i in range(N - 1):
    print(x[i], y[i])
### BUGGY CODE ###

from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = input()
    if command[0] == "i":
        que.appendleft(command[7:])
    elif command[6] == " ":
        try:
            que.remove(command[7:])
        except:
            pass
    elif command[6] == "F":
        que.popleft()
    else:
        que.pop()
print(" ".join(que))

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
que = deque()

for i in range(n):
    command = sys.stdin.readline()[:-1]
    if command[0] == "i":
        que.appendleft(command[7:])
    elif command[6] == " ":
        try:
            que.remove(command[7:])
        except:
            pass
    elif command[6] == "F":
        que.popleft()
    else:
        que.pop()
print(*que)
### BUGGY CODE ###

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

same = N / 2

d.sort()

distribution = [0] * d[len(d) - 1]
total = 0
for di in d:
    num = d.count(di)
    distribution[di - 1] = num

total = 0
totals = [0] * d[len(d) - 1]
num = 0
for i in range(len(distribution)):
    total += distribution[i]
    totals[i] = total
    
    if totals[i] == same:
        num += 1

print(num)


### FIXED CODE ###

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

same = N / 2

# d.sort()

# distribution = [0] * d[len(d) - 1]
# total = 0
# for di in d:
#     num = d.count(di)
#     distribution[di - 1] = num

table = {}
for di in d:
    table[di] = 1 if table.get(di) is None else table.get(di) + 1
table = sorted(table.items())

total = 0
start = 0
end = 0
for difficulty, num in table:
    total += num

    if start == 0 and total == same:
        start = difficulty
    elif start != 0:
        end = difficulty
        break

# print(table, start, end)

answer = end - start
print(answer)
### BUGGY CODE ###

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

b = []
for x in a:
    b.append(x)
    b = list(reversed(b))

print(' '.join(b))

### FIXED CODE ###

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

b = ['' for _ in range(n)]
m = n // 2

b[m] = a[0]

p = 1

for i in range(1, n):
    if i % 2 == 1:
        b[m - p] = a[i]
    else:
        b[m + p] = a[i]
        p += 1

if n % 2 == 1:
    b = list(reversed(b))

print(' '.join(b))
### BUGGY CODE ###

import itertools

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

ans = 0

for i in itertools.combinations(A_int_list, 2):
    ans += i[0] * i[1]

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

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

ans = 0
sum_A = sum(A_int_list)

for i in range(len(A_int_list)):
    sum_A -= A_int_list[i]
    ans += A_int_list[i] * sum_A


print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

s = str(input())
K = I()
n = len(s)

a = set()
for i in range(n):
    for j in range(i+1,n+1):
        a.add(s[i:j])

a = list(a)
a.sort()
print(a[K-1])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

s = str(input())
K = I()
n = len(s)

a = set()
for i in range(n):
    for j in range(i+1,min(i+6,n+1)):
        a.add(s[i:j])

a = list(a)
a.sort()
print(a[K-1])
### BUGGY CODE ###

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

tablef = []
for mi in range(m + 1):
    # tablef.append(table2jou[mi] % m)
    tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    an = tablef[pre_an]
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)


### FIXED CODE ###

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))

is_used = [0] * (m + 1)

count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if is_used[an] == 1:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    is_used[an] = 1
    count = count + an
    pre_an = an

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

import heapq

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
S = [[c for c in input()] for _ in range(H)]


h = []
heapq.heappush(h, (0, Ch, Cw))

while len(h) != 0:
    d, nh, nw = heapq.heappop(h)
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] == ".":
                    S[newh][neww] = str(newd)
                    heapq.heappush(h, (newd, newh, neww))
                elif S[newh][neww] == "#":
                    continue
                else:
                    if int(S[newh][neww]) > newd:
                        S[newh][neww] = str(newd)
                        heapq.heappush(h, (newd, newh, neww))
print(-1)


### FIXED CODE ###

from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
S = [list(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


"""h = []
heapq.heappush(h, (0, Ch, Cw))"""

q = deque()
q.append((0, Ch, Cw))
S[Ch][Cw] = 0

while len(q) != 0:
    d, nh, nw = q.popleft()
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            flag = False
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
                flag = True
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        if flag:
                            q.appendleft((newd, newh, neww))
                        else:
                            q.append((newd, newh, neww))   
print(-1)
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {(i,j):[0,0] for i in range(H) for j in range(W)}
for j in range(W):
    cnt = 0
    cur = 0
    for i in range(H):
        if S[i][j]=="#":
            for i1 in range(cur,i):
                C[(i1,j)][0] = cnt
            cnt = 0
            cur = i+1
        else:
            cnt += 1
    for i1 in range(cur,H):
        C[(i1,j)][0] = cnt
for i in range(H):
    cnt = 0
    cur = 0
    for j in range(W):
        if S[i][j]=="#":
            for j1 in range(cur,j):
                C[(i,j1)][1] = cnt
            cnt = 0
            cur = j+1
        else:
            cnt += 1
    for j1 in range(cur,W):
        C[(i,j1)][1] = cnt
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,sum(C[(i,j)]))
print(cmax-1)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and S[i][j]==".":
            L[i][j] = 1
        elif j>0 and S[i][j]==".":
            L[i][j] = L[i][j-1]+1
        if i==0 and S[i][j]==".":
            U[i][j] = 1
        elif i>0 and S[i][j]==".":
            U[i][j] = U[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if j==W-1 and S[i][j]==".":
            R[i][j] = 1
        elif j<W-1 and S[i][j]==".":
            R[i][j] = R[i][j+1]+1
        if i==H-1 and S[i][j]==".":
            D[i][j] = 1
        elif i>0 and S[i][j]==".":
            D[i][j] = D[i+1][j]+1
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(cmax)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, K = map(int, input().split())
h_list = [int(input()) for i in range(N)]

h_list.sort()
best = 1000000000
for i in range(N - K + 1):
    diff = h_list[i:i+K][-1] - h_list[i:i+K][0]
    if diff < best:
        best = diff

print (best)

### FIXED CODE ###

# -*- coding: utf-8 -*-

N, K = map(int, input().split())
h_list = [int(input()) for i in range(N)]

h_list.sort()
'''
best = 1000000000
for i in range(N - K + 1):
    diff = h_list[i:i+K][-1] - h_list[i:i+K][0]
    if diff < best:
        best = diff
'''
print (min(h_list[i+K-1] - h_list[i] for i in range(N-K+1)))
### BUGGY CODE ###

import sys
def check(t,x,y,nt,nx,ny):
    # print(t)
    # print(x)
    # print(y)
    tempt = nt
    tempx = nx
    tempy = ny
    judge = True
    if (x+y) > (nx+ny+t):
        print("No")
        sys.exit()
    #x方向の移動
    while x != tempx:
        if (x>tempx):
            tempx += 1
            tempt += 1
        elif(x<tempx):
            tempx -= 1
            tempt += 1
    #y方向の移動
    if tempt<=t:
        while y != tempy:
            if (y>tempy):
                tempy += 1
                tempt += 1
            elif(x<tempy):
                tempy -= 1
                tempt += 1
    else:
        print("No")
        sys.exit()
    if (t-tempt)%2 != 0:
        print("No")
        sys.exit()     

    return tempt,tempx,tempy
N = int(input())
nt = 0
nx = 0
ny = 0
t = []
x = []
y = []
#入力
for i in range(N):
    temp = input().split(" ")
    t.append(temp[0])
    x.append(temp[1])
    y.append(temp[2])

for i in range(N):
    na,nb,nc = check(int(t[i]), int(x[i]), int(y[i]),nt,nx,ny)

print("Yes")

### FIXED CODE ###

import sys
def check_ans(t,x,y,nt,nx,ny):
    if (x+y) > (nx+ny+t):
        print("No")
        sys.exit()    
    if (x >= nx):
        nt += (x-nx)
    elif(x <= nx):
        nt += (nx-x)
    if (y >= ny):
        nt += (y-ny)
    elif(y <= ny):
        nt += (ny-y)
    if (t-nt)%2 != 0:
        print("No")
        sys.exit()

N = int(input())
nt = 0
nx = 0
ny = 0
t = []
x = []
y = []
#入力
for i in range(N):
    temp = input().split(" ")
    t.append(temp[0])
    x.append(temp[1])
    y.append(temp[2])
for i in range(N):
    if i == 0:
        check_ans(int(t[i]), int(x[i]), int(y[i]), nt, nx, ny)
    else:
        nt = int(t[i-1])
        nx = int(x[i-1])
        ny = int(y[i-1])
    check_ans(int(t[i]), int(x[i]), int(y[i]), nt, nx, ny)
print("Yes")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

# 整数の入力
N = int(input())
s = 0

while N//10 != 0 or  N%10 !=0:
    s += N%10
    N //= 10

if s % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

# 整数の入力
N = int(input())
# s = 0

# while N//10 != 0 or  N%10 !=0:
#     s += N%10
#     N //= 10

if N % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
while q:
    x,y,l=q.popleft()
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H and s[ny][nx]=='.':
            q.append((nx,ny,l+1))
else:
    print(-1)
    


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)
### BUGGY CODE ###

import os, sys, re, math

N = int(input())

print(sum([i for i in range(1, N)]))


### FIXED CODE ###

import os, sys, re, math

N = int(input())

s = (1 + (N - 1)) * (N // 2)
if (N - 1) % 2 == 1:
    s -= N // 2

print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#n=list(map(int,input().split()))
n = int(input()) 
num = [input() for _ in range(n)] 

for i in range(n):
    print(max(num[:i]+num[i+1:]))
    
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input()) 
num = [input() for _ in range(n)] 
num = np.array(num).astype("int64")
#ma=max(num)
#ind=num.index(ma)
sorted_num=sorted(num)
ma=sorted_num[-1]
ma2=sorted_num[-2]
for i in range(n):
    if ma != num[i]:
        print(str(ma).strip())
    else:
        print(str(ma2).strip())
### BUGGY CODE ###

n = int(input())
xd = [list(map(int, input().split())) for _ in range(n)]
mod = 998244353
INF = 10 ** 18

xx = [[x, x + d, i] for i, (x, d) in enumerate(xd, 1)]
xx.sort()
adj = [[] for _ in range(n + 1)]
stack = [[INF, 0]]
for l, r, i in xx:
    while stack[-1][0] <= l:
        stack.pop()

    ip = stack[-1][1]
    adj[ip].append(i)
    stack.append([r, i])

stack = [0]
d = [-1] * (n + 1)
d[0] = 0
c = [[] for _ in range(n + 1)]
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            c[u].append(v)
            stack.append(v)

dp = [1] * (n + 1)
for u in order[::-1]:
    for v in c[u]:
        dp[u] *= dp[v]
        dp[u] %= mod

    dp[u] += 1
    dp[u] %= mod

ans = dp[0] - 1
ans %= mod
print(ans)


### FIXED CODE ###

def main():
    n = int(input())
    xd = [map(int, input().split()) for _ in range(n)]
    mod = 998244353
    INF = 10 ** 10

    xx = [(x, x + d, i) for i, (x, d) in enumerate(xd, 1)]
    xx.sort()
    adj = [[] for _ in range(n + 1)]
    stack = [(INF, 0)]
    for l, r, i in xx:
        while stack[-1][0] <= l:
            stack.pop()

        ip = stack[-1][1]
        adj[ip].append(i)
        stack.append((r, i))

    stack2 = [0]
    d = [-1] * (n + 1)
    d[0] = 0
    c = [[] for _ in range(n + 1)]
    order = []
    while stack2:
        u = stack2.pop()
        order.append(u)
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                c[u].append(v)
                stack2.append(v)

    dp = [1] * (n + 1)
    for u in order[::-1]:
        for v in c[u]:
            dp[u] *= dp[v]
            dp[u] %= mod

        dp[u] += 1
        dp[u] %= mod

    ans = dp[0] - 1
    ans %= mod
    print(ans)


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

from collections import Counter


N=int(input())
l=['']*N
for i in range(N):
    l[i]=input()

c = Counter(l).most_common()
top=c.pop(0)
ans=[top[0]]
freq=top[1]

while len(c) > 0:
    top=c.pop(0)
    if top[1] == freq:
        ans.append(top[0])
    else:
        break

ans.sort()

for e in ans:
    print(e)

### FIXED CODE ###

from collections import Counter


N=int(input())
l=['']*N
for i in range(N):
    l[i]=input()

l.sort()

c=1
c_crt=1
pre=""
ans=[]
for e in l+[""]:
    if e == pre:
        c_crt+=1
    else:
        if c_crt > c:
            ans=[pre]
            c=c_crt
        elif c_crt == c:
            ans.append(pre)
        c_crt=1
    pre=e
for e in ans:
    print(e)
### BUGGY CODE ###

def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    digit = 1
    for i, c in enumerate(s[::-1]):
        # No time to pow.
        temp += int(c) * digit
        rem[temp % 2019] += 1
        digit *= 10

    return sum(c * (c - 1) // 2 for c in rem)


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

# https://www.hamayanhamayan.com/entry/2020/04/26/232032
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力