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

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)

selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])

scorelist = []
scorelist.append(score)
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for item in selected[::-1]:
        if([elem for elem in selected if(elem[0]==item[0] and elem is not item)]):
            score -= item[1]
            selected.remove(item)
            break

    #add the largest one that add kind
    for j in range(k,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            
            score += 2*startKindNum + 1 + sushi[j][1]
            startKindNum += 1
            scorelist.append(score)
            break
print(max(scorelist))


### FIXED CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)
'''
selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
'''
kindset = set([])
score = 0
extras = []
for item in sushi[:k]:
    if item[0] in kindset:
        extras.append(item[1])
    else:
        kindset.add(item[0])
    score += item[1]
score += len(kindset)**2
maxscore = score
for item in sushi[k:]:
    if not  extras:
        break
    if item[0] in kindset:
        continue
    score += (item[1] - extras.pop()) + 2*len(kindset) + 1
    kindset.add(item[0])
    #print(score)
    if score > maxscore:
        maxscore = score


print(maxscore)
### BUGGY CODE ###

from itertools import accumulate

Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = map(int,input().split())

r = max(R)
A = list(range(2, r+1))
sqrt_r = r**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_r:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

B = [0]*(r+1)
for i in A:
    if int((i+1)/2) in A:
        B[i] = 1

B = list(accumulate(B))

for i,j in zip(L,R):
    print(B[j]-B[i-1])


### FIXED CODE ###

import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]
        wa = a+b
        s = bisect.bisect_left(l[j+1:],wa)
        count += s
        # print(l,a,b,s)
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect.bisect_left(l,l[i]+l[j]) - j - 1
print(count)
### BUGGY CODE ###

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

zumi = []
ima = 1
for i in range(K):
    # 行ったことある町を通る＝ループする
    if ima in zumi:
        zumi.append(ima)
        break
    # 同じ町へテレポートしている
    if ima == A[ima-1]:
        print(ima)
        exit(0)
    zumi.append(ima)
    ima = A[ima-1]
else:
    print(ima)
    exit(0)

loop_s = zumi.index(zumi[-1])
zan_loop = K-loop_s
loop = zumi[loop_s:-1]
amari = zan_loop % (len(zumi)-loop_s-1)
print(loop[amari])


### FIXED CODE ###

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

zumi_hash = {}
zumi = [-1]*(2*(10**5))
ima = 1
for i in range(K):
    # 行ったことある町を通る＝ループする
    if ima in zumi_hash:
        zumi[i] = ima
        break
    # 同じ町へテレポートしている
    if ima == A[ima-1]:
        print(ima)
        exit(0)
    zumi_hash[ima] = True
    zumi[i] = ima
    ima = A[ima-1]
else:
    print(ima)
    exit(0)

loop_e = zumi.index(-1)
loop_s = zumi.index(zumi[loop_e-1])
zan_loop = K-loop_s
loop = zumi[loop_s:loop_e-1]
amari = zan_loop % (len(loop))
print(loop[amari])
### BUGGY CODE ###

N=int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    count = 0
    for j in A:
        if i == j:
            count += 1
    print(count)






### FIXED CODE ###

num = int(input())
table = list(map(int, input().split()))
table2 = []
for i in range(num):
    table2.append(0)
 
for j in range(len(table)):
    table2[table[j]-1] += 1
 
for k in table2:
    print(k)
### BUGGY CODE ###

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

mod = 10**9 + 7

def nCr(n, r):
    if n < r:
        return 0
    r = min(r, n-r)
    num, den = 1, 1
    for i in range(r):
        num = (num * (n-i)) % mod
        den = (den * pow(i+1, mod-2, mod)) % mod
    return num * den % mod

for i in range(1, k+1):
    print(nCr(k-1, i-1) * nCr(n-k+1, i) % mod)

### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n, r):
	if n < r:
		return 0
	r = min(n-r, r)
	if r == 0:
		return 1
	numer = reduce(mul, range(n, n-r, -1))
	denom = reduce(mul, range(1, r+1))
	return numer // denom % mod

N, K = map(int, input().split())
mod = 10**9 + 7

for i in range(1, K+1):
	print(cmb(K-1, i-1) * cmb(N-K+1, i) % mod)
### BUGGY CODE ###

N, M = map(int, input().split())

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

for i in range(M):
	max_index = A.index(max(A))
	A[max_index] = int(A[max_index]/2)

print(sum(A))



### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

A = [int(i)*(-1) for i in input().split()]



# print(A)
# for i in range(M):
# 	max_index = A.index(max(A))
# 	A[max_index] = int(A[max_index]/2)

# print(sum(A))
heapq.heapify(A)

for i in range(M):
	

	min = heapq.heappop(A)
	# 最小値を削除と値を渡す
	# print(A)
	# print(min)

	heapq.heappush(A,int(min/2))
	# print(A)


print(sum(A)*(-1))
### BUGGY CODE ###

s = raw_input()
n = 0

def mul(s):
    if len(s) < 3:
        return 0
    n = 0
    _res = 0
    j = 0
    while j < (len(s) - 2):
        j = j + _res
        if j < 0:
            j = 0
        _res = 0
        str = s[j:(j + 3)]
        if str == "ABC":
            n = n + 1
            _res = -2
            s = s[:j] + "BCA" + s[j + 3:]
    return n
print mul(s)

### FIXED CODE ###

def test(s):

	res = 0
	aAdd = 0
	last = ''
	tmp = ''
	for i in xrange(len(s)):
		if tmp and tmp > i:
			continue
		if s[i] == 'A':
			aAdd += 1
		elif s[i:i+2] == 'BC':
			# print aAdd
			res = res + aAdd
			tmp = i + 2
		else:
			aAdd = 0
			last = s[i]


	return res
s=raw_input()
print test(s)
### BUGGY CODE ###

A,B, C, K = map(int,input().split())
flag = 1
for k in range(K):
  A,B,C = B+C, C+A, A+B
  if abs(A-B) > 10**18:
    print("Unfair")
    flag = 0
    break
if flag:
  print(A-B)

### FIXED CODE ###

A,B, C, K = map(int,input().split())
if K%2==0:
  print(A-B)
else:
  print(B-A)
### BUGGY CODE ###

k = int(input())
keta = len(str(k))
now = '7' * keta
ans = -1
while len(now) <= 999982:
    if int(now) % k == 0:
        ans = len(now)
        break
    now += '7'
print(ans)



### FIXED CODE ###

import sys
k = int(input())
mod_k = [0] * (k+2)
mod_k[1] = 7 % k
if mod_k[1] == 0:
    print(1)
    sys.exit()
for i in range(2,k+2):
    nex = (mod_k[i-1]*10+7) % k
    if nex == 0:
        print(i)
        sys.exit()
    mod_k[i] = nex
print(-1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = [a[i] if (i % 2 == 0) else -1 * a[i] for i in range(n)]
b = []
for i in range(n):
    t = a[i:] + a[:i]
    ttt = sum([t[i] if (i % 2 == 0) else -1 * t[i] for i in range(n)])
    b.append(str(ttt))
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = [a[i] if (i % 2 == 0) else -1 * a[i] for i in range(n)]
b = []
ans0 = sum([a[i] if (i % 2 == 0) else -1 * a[i] for i in range(n)])
b.append(str(ans0))
temp = int(ans0 // 2)
for i in range(0, n-1):
    k = a[i] - temp
    b.append(str(k*2))
    temp = k
print(' '.join(b))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""

def kenzan(m, n, A):

    # ?????????????????§????????°???????????£????????????
    nA = []
    max = 0
    min = 2000
    total = 0
    for i in range(n):
        if A[i] == m:
            return 0
        elif A[i] < m:
            nA.append(A[i])
        if max < A[i]:
            max = A[i]
        if min > A[i]:
            min = A[i]
        total += A[i]

    n =len(nA)

    if m > total:
        return -1
    elif m < min:
        return -1

    l = 2 ** n
    for i in range(l):
        mask = 1
        c = 0
        for j in range(n):
            b = i & mask
            if b != 0:
                x = c + nA[j]
#                print("{0:2}/{1:2} {6:08b} m[{2:4}] c+Aj[{3:4}] c[{4:4}] Aj[{5:4}]".format(i, mask, m, x, c, nA[j], b))
                if x == m:
                    return 0
                elif x > m:
                    break
                else:
                    c = x
            mask <<= 1
    return -1
 
def main():
    """ ????????? """
    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))

    for i in range(q):
        if kenzan(M[i], n, A) == 0:
            print("yes")
        else:
            print("no")


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
?????? n ?????°??? A ??¨??´??° m ???????????????A ???????´?????????????????????????????´?????¶????????????????
m ???????????????????????????????????????????????°????????????????????????????????????
AA ??????????´???????????????????????????¨?????§????????????

??°??? A ??????????????????????????§???????????¨?????? q ?????? mi ????????????????????§???
???????????????????????? "yes" ????????? "no" ??¨???????????????????????????

n ??? 20 ; q ??? 200 ; 1 ??? A???????´? ??? 2000 ; 1 ??? Mi ??? 2000

"""

def main():
    """ ????????? """
    n = int(input())
    A = sorted(map(int,input().split()))
    q = int(input())
    M = list(map(int,input().split()))
    g = 0

    tA = []
    l = 2 ** n
    for i in range(1,l):
        c = 0
        bi = "{0:0{width}b}".format(i,width=n)
        bi = bi[::-1]
        for j in range(n):
            if bi[j] == "1":
                c += A[j]
        tA.append(c)
#    tA.sort()

    for mi in M:
        if mi in tA:
            print("yes")
        else:
            print("no")

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

l,r=map(int,input().split())
a=[i%2019 for i in range(l,r+1)]
set(a)
ans=2018
for i in a:
    for j in a:
        if i!=j:
            ans=min(ans,(i*j)%2019)
print(ans)

### FIXED CODE ###

l,r=map(int,input().split())
a=[i%2019 for i in range(l,min(r+1,l+2020))]
ans=2018
for i in a:
    for j in a:
        if i!=j:
            ans=min(ans,(i*j)%2019)
print(ans)
### BUGGY CODE ###

import queue

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))


### FIXED CODE ###

from collections import deque

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = deque()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.append((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(len(que)):
    p = que.popleft()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.append((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))
### BUGGY CODE ###

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))
cc = c[:]
  
q = [(0,x1-1,y1-1,0,())]
while(q):
  qq = []
  for a,x,y,kk,d in q:
    #print(x,y,c[x][y])
    if cc[x][y] == '.':
      cc[x][y] = (a,kk)
    else:
      if a < cc[x][y][0] or (a == cc[x][y][0] and kk >= cc[x][y][1]):
        cc[x][y] = (a,kk)
      else:
        continue
    # c[x][y] = min(c[x][y],a)
    # c[x][y] = a
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      if 0 <= x+dx < h and 0 <= y+dy < w and c[x+dx][y+dy] != '@':
        if kk == 0 or d != (dx,dy):
          nk = k-1
          na = a+1
        else:
          nk = kk-1
          na = a
        if cc[x+dx][y+dy] == '.' or na < cc[x+dx][y+dy][0] or (na == cc[x+dx][y+dy][0] and kk >= cc[x+dx][y+dy][1]):
          qq.append((na,x+dx,y+dy,nk,(dx,dy)))
  #print(qq)
  q = qq[:]

print(-1 if cc[x2-1][y2-1] == '.' else cc[x2-1][y2-1][0])
#print(c)

### FIXED CODE ###

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
          break
        if c[xx][yy] == '.' or (c[xx][yy] != '.' and c[xx][yy] > a):
          c[xx][yy] = a
          qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)
### BUGGY CODE ###

import sys
N, K = map(int,input().split())
Alist = list(map(int,input().split()))
Flist = list(map(int,input().split()))
Alist.sort()
sum_Alist = 0
for i in range(N):
    sum_Alist += Alist[i]
print(Alist,Flist,file=sys.stderr)
if sum_Alist <= K:
    print(0)
    exit()
maxtime = max(Alist)*max(Flist)
mintime = -1
print(maxtime,mintime,file=sys.stderr)
while mintime+1 < maxtime:
    mid = (mintime+maxtime)//2
    sum_midlist = 0
    max_midlist = 0
    midlist = [0 for i in range(N)]
    for i in range(N):
        midlist[i] = mid//Flist[i]
    midlist.sort()
    for i in range(N):
        if midlist[i] < Alist[i]:
            sum_midlist += Alist[i]-midlist[i]
    print(maxtime,mintime,sum_midlist,file=sys.stderr)
    if sum_midlist <= K:
        maxtime = mid
    else:
        mintime = mid
print(maxtime)

### FIXED CODE ###

import sys
N, K = map(int,input().split())
Alist = list(map(int,input().split()))
Flist = list(map(int,input().split()))
Alist.sort()
sum_Alist = 0
for i in range(N):
    sum_Alist += Alist[i]
print(Alist,Flist,file=sys.stderr)
if sum_Alist <= K:
    print(0)
    exit()
maxtime = max(Alist)*max(Flist)
mintime = -1
print(maxtime,mintime,file=sys.stderr)
midlist = [0 for i in range(N)]
while mintime+1 < maxtime:
    mid = (mintime+maxtime)//2
    sum_midlist = 0
    max_midlist = 0
    for i in range(N):
        midlist[i] = mid//Flist[i]
    midlist.sort()
    for i in range(N):
        if midlist[i] < Alist[i]:
            sum_midlist += Alist[i]-midlist[i]
    #print(maxtime,mintime,sum_midlist,file=sys.stderr)
    if sum_midlist <= K:
        maxtime = mid
    else:
        mintime = mid
print(maxtime)
### BUGGY CODE ###

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

dp = [[[0] * 2501 for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(2501):
            if k + x[i] <= 2500:
                dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]


ans = 0
for j in range(1, n+1):
    ans += dp[n][j][j * a]

print(ans)

### FIXED CODE ###

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

dp = [[[0] * 2501 for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(n):
        for k in range(2501):
            if k + x[i] <= 2500:
                dp[i+1][j+1][k+x[i]] += dp[i][j][k]
            dp[i+1][j][k] += dp[i][j][k]


ans = 0
for j in range(1, n+1):
    ans += dp[n][j][j * a]

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


n,m=map(int,input().split())
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
maxim=(10**3)*2
mod=10**9+7
dp=[[0 for i in range(m+1)]for j in range(n+1)]

for i in range(n):
    for j in range(m):
        x=0
        if s[i]==t[j]:
            x=dp[i][j]+1
        dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j]+x)%mod
#print(dp)
print((dp[n][m]+1)%mod)


### FIXED CODE ###

n,m=map(int,input().split())
s=[int(i) for i in input().split()]
t=[int(i) for i in input().split()]
mod=10**9+7
dp=[[0 for i in range(m+1)]for j in range(n+1)]
for i in range(n):
    for j in range(m):
        x=0
        if s[i]==t[j]:
            x=dp[i][j]+1
        dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j]+x)%mod
#print(dp)
print((dp[n][m]+1)%mod)
### BUGGY CODE ###

N = int(input())
lst = [int(i) for i in input().split()]
lst.insert(0, 0)
res = [0]
for i in range(1, N+1):
    t = lst[:]
    del(t[i])
    k = 0
    for i in range(1, len(t)):
        k += abs(t[i] - t[i-1])
    res.append(sum([abs(t[i] - t[i-1]) for i in range(1, N)]) + abs(t[-1]))

for i in range(1, N+1):
    print(res[i])


### FIXED CODE ###

x = int(raw_input())
s = raw_input().split(" ")
s.insert(0, "0")

def cost(a, b):
 return abs(int(a)-int(b))

totalCost = cost(s[-1], s[0])
skipGain = [None] * (x+1)

costPrev = cost(s[0], s[1])
for i in range(0, x):#i=0 skipping 1st one, prev=0-1, post=1-2
 costThisOne = cost(s[i+1], s[0 if i==x-1 else i+2])
 totalCost += costPrev
 skipGain[i+1] = cost(s[i], s[0 if i==x-1 else i+2]) - costPrev - costThisOne
 costPrev = costThisOne

for i in range(1, x+1):
 print totalCost + skipGain[i]
### BUGGY CODE ###

N = int(input())

ans = 0

for i in range(1,N+1):
    for j in range(1,N+1):
        if N - i*j > 0:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0

for A in range(1,N):
    ans += (N-1)//A
        
print(int(ans))
### BUGGY CODE ###

MOD=2019

S=list(int(s) for s in input()[::-1])
T=[S[0]]
for i in range(1,len(S)):
    T.append(T[-1]+S[i]*(10**i))
cnt={}
for i in range(2019):
    cnt[i]=0
for t in T:
    cnt[t%MOD]+=1
ans=0
for i in range(2019):
    c=cnt[i]
    if c>=2:
        ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)

### FIXED CODE ###

MOD=2019

S=list(int(s) for s in input()[::-1])
T=[S[0]]
for i in range(1,len(S)):
    T.append(T[-1]+S[i]*pow(10,i,MOD))
cnt={}
for i in range(2019):
    cnt[i]=0
for t in T:
    cnt[t%MOD]+=1
ans=0
for i in range(2019):
    c=cnt[i]
    if c>=2:
        ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
c1 = 0
c2 = 0 
c3 = 0
for i in range(N):
    if a[i] == 1:
        c1 += 1
    if a[i] == 2:
        c2 += 1
    if a[i] == 3:
        c3 += 1
dp= [[[-1] * (N+1) for i in range(N+1)] for j in range(N+1)]
dp[c1][c2][c3] = 0
def solve(c1, c2, c3):
    if dp[c1][c2][c3] > 0:
        return dp[c1][c2][c3]
    if c1 == c2 == c3 == 0:
        return 0
    res = 1/(1-(N-c1-c2-c3)/N)
    if c1 > 0:
        res += solve(c1-1,c2,c3)*(c1/N)/(1-(N-c1-c2-c3)/N)
    if c2 > 0:
        res += solve(c1+1,c2-1,c3)*(c2/N)/(1-(N-c1-c2-c3)/N)
    if c3 > 0:
        res += solve(c1,c2+1,c3-1)*(c3/N)/(1-(N-c1-c2-c3)/N)
    dp[c1][c2][c3] = res
    return dp[c1][c2][c3]
print(solve(c1, c2, c3))

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
c1 = 0
c2 = 0 
c3 = 0
for i in range(N):
    if a[i] == 1:
        c1 += 1
    if a[i] == 2:
        c2 += 1
    if a[i] == 3:
        c3 += 1
dp= [[[0] * (N+1) for i in range(N+1)] for j in range(N+1)]
for k in range(c3+1):
    for j in range(c3+c2-k+1):
        for i in range(N-j-k+1):
            if i == j == k == 0:
                continue
            else:
                res = N
                if i > 0:
                    res += dp[k][j][i-1]*i
                if j > 0:
                    res += dp[k][j-1][i+1]*j
                if k > 0:
                    res += dp[k-1][j+1][i]*k
                dp[k][j][i] = res/(i+j+k)
print(dp[c3][c2][c1])
### BUGGY CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0]=1
for i in range(1,N+1) : 
    for j in range(S + 1) : 
        if(j==0):
            dp[i][j]=2**i
            dp[i][j]%=mod
        else:
            dp[i][j]+=2*dp[i-1][j]
            dp[i][j]%=mod
            if(j-A[i-1]>=0):
                dp[i][j]+=dp[i-1][j-A[i-1]]
                dp[i][j]%=mod
print(dp[N][S]%mod)

### FIXED CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])
### BUGGY CODE ###

n,k,q=map(int,input().split())
A=[int(input()) for i in range(q)]

tensu=[]
for i in range(n):
    tensu.append(k)

for i in range(q):
    for j in range(n):
        if j!=A[i]-1:
            tensu[j]=tensu[j]-1

for i in range(n):
    if tensu[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
A=[int(input()) for i in range(q)]

tokuten=[0]*n

for i in range(q):
    tokuten[A[i-1]-1]=tokuten[A[i-1]-1]+1

for i in range(n):
    if tokuten[i]>q-k:
        print("Yes")
    else:
        print("No")