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

N = int(input())
ab = [list(map(int, input().split())) for i in range(N)]
ab = sorted(ab, key=lambda x: x[1])
for i in range(N):
    for j in range(i, N):
        ab[j][1] -= ab[i][0]
        if ab[j][1] < 0:
            print("No")
            exit()
print("Yes")


### FIXED CODE ###

N = int(input())
ab = [[0, 0]] + [list(map(int, input().split())) for i in range(N)]
ab = sorted(ab, key=lambda x: x[1])
for i in range(len(ab) - 1):
    ab[i + 1][0] += ab[i][0]
    if ab[i + 1][1] < ab[i + 1][0]:
        print("No")
        exit()

print("Yes")
### BUGGY CODE ###

H, W = map(int, input().split())
board = []
visited = [[False for _ in range(W)] for _ in range(H)]
goal_dst = [[float("inf") for _ in range(W)] for _ in range(H)]
no = 0

for _ in range(H):
	board.append(list(map(str, input())))
	no += board[-1].count("#")
	
# bfsで最短路を求める
Q = [[0, 0, 1]]
juuji = [[-1, 0], [1, 0], [0, -1], [0, 1]]

while Q:
	cur = Q.pop(0)
	visited[cur[0]][cur[1]] = True
	dist = cur[2]
	if goal_dst[cur[0]][cur[1]] < dist: continue
	goal_dst[cur[0]][cur[1]] = dist
	for move in juuji:
		new_y = cur[0] + move[0]
		new_x = cur[1] + move[1]
		if not (0 <= new_x and new_x <= W - 1 and 0 <= new_y and new_y <= H - 1): continue 
		if board[new_y][new_x] == "." and visited[new_y][new_x] == False:
			Q.append([new_y, new_x, dist + 1])
			
if goal_dst[-1][-1] == float("inf"):
	print(-1)
else:
	print(H * W - goal_dst[-1][-1] - no)

### FIXED CODE ###

from heapq import heappush, heappop
H, W = map(int, input().split())
s = [input() for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
q = [(0, 0, 0)]
while q :
    cost, cx, cy = heappop(q)
    if cost >= dist[cy][cx] :
        continue
    dist[cy][cx] = cost
        
    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
        if 0 <= cx + dx < W and 0 <= cy + dy < H and s[cy+dy][cx+dx] != '#' :
            heappush(q, (cost+1, cx+dx, cy+dy))
            
if dist[H-1][W-1] == float('inf') :
    print(-1)
else :
    ret = 0
    for s_ in s :
        ret += s_.count('#')
    print(H * W - ret - dist[H-1][W-1] - 1)
### BUGGY CODE ###

from collections import deque

S = input()

ss = []
flag = True
ans = 0
for i in range(len(S)): ss.append(S[i])

while flag:
    length = len(ss)
    tmp_flag = False
    for i in range(length-1):
        if ss[i] != ss[i+1]:
            rm = i
            ans += 2
            tmp_flag = True
            break
    if tmp_flag:
        ss.pop(rm)
        ss.pop(rm)
    else:
        flag = False
    
print(ans)


### FIXED CODE ###

S = input()

ss = []
ans = 0
for i in range(len(S)): ss.append(S[i])

zeros = 0
ones = 0

for i in range(len(ss)):
    if ss[i] == "0":
        zeros += 1
    elif ss[i] == "1":
        ones += 1

ans = 2*min(zeros, ones)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

ans = len(s)

for i in range(len(s)):
    func  = lambda x, y, v: y < x and v != "E" or y > x and v != "W"
    tmp = len([1 for j, v in enumerate(s) if func(i, j, v)])

    ans = min(tmp, ans)

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ans = s.count("E")

tmp = ans

for i in s:
    tmp += (-1 if i == "E" else 1)
    ans = min(ans, tmp)

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

n = int(input())
lis = [x for x in input().split()]
ans = 0
for i in range(n):
  if  lis.count(lis[i]) >= 2:
    ans += 1
    break

if ans == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n = int(input())
lis = [x for x in input().split()]
lis.sort()

for i in range(1, n):
  if lis[i-1] == lis[i]:
    print("NO")
    exit()
  
print("YES")
### BUGGY CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))

tmp=abs(X-min(x))
isFinished=0
for i in range(tmp,0,-1):
    if tmp%i==0:
        canDivide=1
        for j in range(N):
            tmp=abs(X-x[j])
            if tmp%i:
                canDivide=0
                break
        if canDivide:
            print(i)
            isFinished=1
            break
    if isFinished:
        break


### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
diffx=[abs(X-x[i]) for i in range(N)]

def euclid(a,b):
    if b==0:
        return a
    else:
        return euclid(b,a%b)

gcd=diffx[0]
for i in range(1,N):
    gcd=euclid(diffx[i],gcd)
print(gcd)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
i = 0
while a:
    if a.count(a[0]) == 1:
        i+=1
    a = list(filter(lambda x: x%a[0] >0,a))
print(i)

### FIXED CODE ###

_,*a = map(int, open(0).read().split())
a.sort()
m = -~a[-1]
c = [0]*m
for i in a:
    c[i] += 1
    if c[i] > 1:
        continue
    for j in range(i * 2, m, i):
        c[j] = 2
print(sum(c[i]==1for i in a))
### BUGGY CODE ###

N, K = map(int,input().split())
P = list(map(int,input().split()))
prob = [0 for _ in range(N)]
for i in range(N):
    prob[i] = (P[i]+1)/2
m = 0
for j in range(N-K+1):
    a = sum(prob[j:(j+K)])
    if a > m:
        m = a
print(m)

### FIXED CODE ###

N, K = map(int,input().split())
P = list(map(int,input().split()))
prob = [0 for _ in range(N)]
for i in range(N):
    prob[i] = (P[i]+1)/2
m = sum(prob[:K])
a = sum(prob[:K])
for j in range(1,N-K+1):
    a = a - prob[j-1] + prob[j+K-1]
    if a > m:
        m = a
print(m)
### BUGGY CODE ###

s=input()
k=int(input())
l=len(s)
a=[]
for i in range(l):
    for j in range(i,l):
        jbreak = False
        sij = s[i:j+1]
        #print(sij)
        if not(sij in a):
            if a==[]:
                a.append(sij)
            elif len(a) < k:
                a.insert(0,sij)
                for m in range(len(a)-1):
                    if a[m]>a[m+1]:
                        a[m],a[m+1]=a[m+1],a[m]
                    else: break
            else:
                a.insert(0,sij)
                breakflag = False
                for m in range(k):
                    if a[m]>a[m+1]:
                        a[m],a[m+1]=a[m+1],a[m]
                    else: 
                        breakflag=True
                        break
                if not(breakflag):jbreak = True
        if j-i>k: break
print(a[k-1])

### FIXED CODE ###

s=input()
k=int(input())
l=len(s)
a={s[i:i+j+1] for i in range(l) for j in range(k+1)}
a=list(a)
a.sort()
print(a[k-1])
### BUGGY CODE ###

from collections import defaultdict
from math import factorial

MOD = 10 ** 9 + 7


def factorize(n):
    facts = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        facts[2] += 1
    m = 3
    while m * m <= n:
        while n % m == 0:
            facts[m] += 1
            n //= m
        m += 2
    if 1 < n:
        facts[n] += 1
    return facts


def nCr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))


N, M = map(int, input().split())
factors = factorize(M)
ans = 1
for p, e in factors.items():
    ans = ans * nCr(N - 1 + e, e) % MOD
print(ans)

### FIXED CODE ###

from collections import defaultdict


def factorize(n):
    facts = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        facts[2] += 1
    m = 3
    while m * m <= n:
        while n % m == 0:
            facts[m] += 1
            n //= m
        m += 2
    if 1 < n:
        facts[n] += 1
    return facts


MOD = 10 ** 9 + 7  # should be a prime number
MAX = 10 ** 5 + 100
FACTS = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    FACTS[i] = FACTS[i - 1] * i % MOD
FACTINVS = [1] * (MAX + 1)
INVS = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    q, r = divmod(MOD, i)
    INVS[i] = -INVS[r] * q % MOD
    FACTINVS[i] = FACTINVS[i - 1] * INVS[i] % MOD


def nCr(n, r):
    return FACTS[n] * FACTINVS[r] * FACTINVS[n - r]


N, M = map(int, input().split())
factors = factorize(M)
ans = 1
for p, e in factors.items():
    ans = ans * nCr(N - 1 + e, e) % MOD
print(ans)
### BUGGY CODE ###

import numpy as np
N, M =map(int, input().split())
a=np.array(list(map(int, input().split()))) 

    
for i in range(M):
  ind=np.argmax(a)
  a[ind] = a[ind]//2
  
print(sum(a))
  
  

  

### FIXED CODE ###

import heapq
import math
N, M =map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(a)


for i in range(M):
  tmp_min = heapq.heappop(a)
  heapq.heappush(a,math.ceil(tmp_min/2))
  
  
print(-sum(a))
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break
            if flg:
                now_kouji.add(position)
            else:
                now_kouji.remove(position)
            now_ind += 1
        if len(now_kouji) == 0:
            ans = -1
        else:
            ans = min(now_kouji)
        print(ans)





if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    ans = 10 ** 9 + 1
    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break

            if flg:
                now_kouji.add(position)
                ans = min(ans, position)
            else:
                now_kouji.remove(position)
                if len(now_kouji) == 0:
                    ans = 10 ** 9 + 1
                elif ans == position:
                    ans = min(now_kouji)

            now_ind += 1
        if ans == 10 ** 9 + 1:
            print(-1)
        else:
            print(ans)





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

n,q=map(int,input().split())
s=input()
num=[0]*n
for i in range(n-1):
    if s[i+1]=="C" and s[i]=="A":
        num[i]+=1
def rtn(num1,num2):
    return sum(num[num1:num2])
for i in range(q):
    l,r=map(int,input().split())
    print(rtn(l-1,r-1))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
num=[0]
for i in range(n-1):
    if s[i+1]=="C" and s[i]=="A":
        num.append(num[-1]+1)
    else:
        num.append(num[-1])
for i in range(q):
    l,r=map(int,input().split())
    print(num[r-1]-num[l-1])
### BUGGY CODE ###

N, W = [int(item) for item in input().split()]
item = [[int(item) for item in input().split()] for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        if 0 <= w - item[i][0]:
            dp[i+1][w] = max(dp[i][w], dp[i][w - item[i][0]] + item[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])


### FIXED CODE ###

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

N, W = [int(item) for item in input().split()]
item = np.array([[int(item) for item in input().split()] for _ in range(N)])


dp = np.full((N+1, 10**5 + 1), 10**12+1)
dp[0][0] = 0

for i in range(N):
    dp[i+1] = dp[i]
    w, v = item[i]
    np.minimum(dp[i][v:], dp[i][:-v] + w, out=dp[i+1][v:])

print(np.where(dp[N] <= W)[0][-1])
### BUGGY CODE ###

import itertools
N=int(input())
A=list(map(int,input().split()))
c=list(itertools.combinations(A,2))
p = 10**9 + 7
ans=0
for i in c:
  ans+= (i[0]*i[1])%p
print(ans%p)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
S=sum(A)
p= 10**9 +7
for i in range(N):
  S-=A[i]
  ans += (A[i]*S)%p
print(ans%p)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque
for i in range(N):
    dist = [-1]*N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    for d in dist:
        if d > 0:
            ans[d - 1] += 1
for a in ans:
    print(a // 2)


### FIXED CODE ###

N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque, Counter

for i in range(N):
    dist = [-1] * N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    dist_Counter = Counter(dist)
    for key, val in dist_Counter.items():
        if key != 0:
            ans[key - 1] += val

for a in ans:
    print(a // 2)
### BUGGY CODE ###

N, M = map(int,input().split())
ID = list(i+1 for i in range(N))

for i in range(M):
  L,R = map(int,input().split())
  ID_new = [j for j in range(L,R+1)]
  ID = set(ID) & set(ID_new)

print(len(ID))

### FIXED CODE ###

N, M = map(int,input().split())
l=1
r=N
for i in range(M):
  L,R = map(int,input().split())
  l = max(l,L)
  r = min(r,R)
ans = r-l+1
if ans >= 0:
  print(ans)
else:
  print(0)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

b = []
r = 1

b.append(a[0])
for i in range(1, n):
    if(r == 1):
        b.append(a[i])
        r = 0
    elif(r == 0):
        b.insert(0, a[i])
        r = 1
    else:
        pass

if(n % 2 == 0):
    b.reverse()
    

print(*b)


### FIXED CODE ###

from collections import *
n = int(input())
a = [int(i) for i in input().split()]

b = deque()

b.append(a[0])
for i in range(1, n):
    if(i%2 == 1):
        b.append(a[i])  
    else:
        b.appendleft(a[i])
   

if(n % 2 == 0):
    b.reverse()
    

print(' '.join(map(str, b)))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
query = [list(map(str,input().split())) for _ in range(q)]
def sim(x):
    now = s[x]
    for i in range(q):
        t,d = query[i][0],query[i][1]
        if now != t:
            continue
        if d == "L":
            x -= 1
            if x == -1:
                return -1
        else:
            x += 1
            if x == n:
                return 1
        now = s[x]
    return 0

max_left = -1
min_right = n
min_safe = n
max_safe = -1
save = (max_left, min_right)
flag = 0
while (min_right-max_left) > 1:
    m = (max_left+min_right)//2
    j = sim(m)
    if j == -1:
        max_left = m
    if j == 0:
        max_safe = max(max_safe, m)
        min_safe = min(min_safe, m)
    if j == 1:
        min_right = m
    
    if (max_left, min_right) != save:
        save = (max_left, min_right)
    else:
        #left
        #print(max_left, min_safe, max_safe, min_right)
        l,r = max_left, min_safe
        while (r-l) > 1:
            m = (r+l)//2
            j = sim(m)
            if j == -1:
                l = m
            elif j == 0:
                r = m
        max_left, min_safe = l,r
        #right
        l,r = max_safe, min_right
        while (r-l) > 1:
            m = (r+l)//2
            j = sim(m)
            if j == 0:
                l = m
            elif j == 1:
                r = m
        max_safe, min_right = l,r

        flag = 1
        break
if flag:
    print(max_safe-min_safe+1)
else:
    print(0)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
query = [list(map(str,input().split())) for _ in range(q)]
def sim(x):
    now = s[x]
    for i in range(q):
        t,d = query[i][0],query[i][1]
        if now != t:
            continue
        if d == "L":
            x -= 1
            if x == -1:
                return -1
        else:
            x += 1
            if x == n:
                return 1
        now = s[x]
    return 0

max_left = -1
min_right = n
min_safe = n
max_safe = -1
save = (max_left, min_right)
flag = 0
while (min_right-max_left) > 1:
    m = (max_left+min_right)//2
    j = sim(m)
    if j == -1:
        max_left = m
    if j == 0:
        max_safe = max(max_safe, m)
        min_safe = min(min_safe, m)
    if j == 1:
        min_right = m
    
    if (max_left, min_right) != save:
        save = (max_left, min_right)
    else:
        #left
        #print(max_left, min_safe, max_safe, min_right)
        l,r = max_left, min_safe
        while (r-l) > 1:
            m = (r+l)//2
            j = sim(m)
            if j == -1:
                l = m
            elif j == 0:
                r = m
        max_left, min_safe = l,r
        #right
        l,r = max_safe, min_right
        while (r-l) > 1:
            m = (r+l)//2
            j = sim(m)
            if j == 0:
                l = m
            elif j == 1:
                r = m
        max_safe, min_right = l,r

        flag = 1
        break
if flag:
    print(max_safe-min_safe+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
S = str(input())


S_R = []
S_G = []
S_B = []


for i in range(N):
    s = S[i]
    if (s == 'R'):
        S_R.append(i)
    if (s == 'G'):
        S_G.append(i)
    if (s == 'B'):
        S_B.append(i)

count = len(S_R) * len(S_G) * len(S_B)
rgb = {'R', 'G', 'B'}


for i in range(N):
    for j in range(i):
        x = S[j::i]
        for a, b, c in zip(x, x[1:], x[2:]):
            if({a,b,c} == rgb):
                count -=1


print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

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

ll = [int(input()) for i in range(a)]

l=[]
for i in range(n):
  l.append(p)

for j in ll:
  for i in range(n):
    if i != j-1:
      l[i] = l[i]-1
      
for i in l:
  if i <=0:
    print("No")
  else:
    print("Yes")

      

### FIXED CODE ###

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

ll = [int(input()) for i in range(a)]


import collections

c = collections.Counter(ll)

for i in range(n):
  if c.get(i+1)==None:
    if p - a > 0:
      print("Yes")
    else:
      print("No")
    continue
  if a - c.get(i+1) >= p:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    for i in range(N):
        t += int(S.pop())*pow(10, i)
        a[t%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

x = int(input())
for i in range(10**8):
    if i**5 == x:
        print(i,0)
        break
    elif i**5 == x-1:
        print(i,-1)
        break

### FIXED CODE ###

import sys
x = int(input())
a = []
b = []
t = 0
for i in range(-1000,1000):
    t = i**5
    a.append([t,i])
    b.append([t,i])
    
for i in a:
    for j in b:
        if i[0]-j[0] == x:
            print(i[1],j[1])
            sys.exit()
### BUGGY CODE ###

from math import factorial
def ncr(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)


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

numList = [0] * (2*(10**5))
numSet = set()

for i in range(len(a)):
    numList[a[i]] += 1
    if(numList[a[i]]==2):
        numSet.add(a[i])

for i in range(len(a)):
    s = 0
    for j in numSet:
        if(j == a[i]):
            if(numList[j]>2):
                s += ncr(numList[j]-1,2)
        else:
            s += ncr(numList[j],2)
    print(s)

    


### FIXED CODE ###

from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


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

numList = [0] * (n+1)
numSet = set()

ncrList = [0] * (n+1)

resultList = [0] * (n+1)
resultSet = set()

for i in range(len(a)):
    numList[a[i]] += 1
    if(numList[a[i]]==2):
        numSet.add(a[i])

sums = 0
for i in numSet:
    ncrList[i] = ncr(numList[i], 2)
    sums += ncrList[i]

for i in range(len(a)):
    if(a[i] in resultSet):
        print(resultList[a[i]])
        continue
    s = sums
    if(a[i] in numSet):
        if(numList[a[i]] == 2):
            s -= 1
        else:
            s -= ncrList[a[i]]
            s += ncr(numList[a[i]]-1, 2)
    print(s)
    resultList[a[i]] = s
    resultSet.add(a[i])
### BUGGY CODE ###

S = input()
n = len(S)
Y = {0:1}
# print(Y)
Y[0] = 1
for i in range(1,n+1):
    k = int(S[-i:])%2019
    if k not in Y:
        Y[k] = 1
    else:
        Y[k] += 1
# print(Y)

c = 0
for y in Y:
    d = Y[y]
    c += d*(d-1)//2
print(c)


### FIXED CODE ###

import time

p0 = time.time()
S = input()
n = len(S)
Y = {0:1}
# print(Y)
Y[0] = 1
A = [0]
pk = 0
for i in range(1,n+1):
    # print(S[-i])
    k = (int(S[-i])*pow(10,i-1,2019)+pk)%2019
    A.append(k)
    if k not in Y:
        Y[k] = 1
    else:
        Y[k] += 1
    pk = k

# print(A)
# print(Y)
# print(time.time()-p0)
c = 0
for y in Y:
    d = Y[y]
    c += d*(d-1)//2
print(c)
### BUGGY CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=pow(10,n-1)
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)


### FIXED CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)