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

#!/usr/bin/env python3
#ABC147 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
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()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

dp = [[set() for _ in range(w)] for _ in range(h)]
lst = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        lst[i][j] = abs(a[i][j] - b[i][j])

dp[0][0].add(lst[0][0])
for i in range(h):
    for j in range(w):
        for k in dp[i][j]:
            if i+1 < h:
                dp[i+1][j].add(k+lst[i+1][j])
                dp[i+1][j].add(abs(k-lst[i+1][j]))
            if j+1 < w:
                dp[i][j+1].add(k+lst[i][j+1])
                dp[i][j+1].add(abs(k-lst[i][j+1]))
ans = inf
for i in dp[-1][-1]:
    ans = min(ans,i)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC147 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
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()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

dp = [[0 for _ in range(w)] for _ in range(h)]
lst = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        lst[i][j] = abs(a[i][j] - b[i][j])

dp[0][0] |= 1 << (6400+lst[0][0])
dp[0][0] |= 1 << (6400-lst[0][0])
for i in range(h):
    for j in range(w):
        t = dp[i][j]
        if i+1 < h:
            dp[i+1][j] |= t << lst[i+1][j]
            dp[i+1][j] |= t >> lst[i+1][j]
        if j+1 < w:
            dp[i][j+1] |= t << lst[i][j+1]
            dp[i][j+1] |= t >> lst[i][j+1]

x = dp[-1][-1]
for i in range(6401)[::-1]:
    if (x >> i) & 1:
        print(6400 - i)
        break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n + 1)]
for d in range(1,n+1):
    for i in range(n-d+1):
        j = i + d
        if (n - i - j) % 2:
            dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
        else:
            dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
print(dp[0][n])


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###

D,N = map(int,input().split())
K = 1
count = 0
while(True):
    A = K
    cnt = 0
    while(A>0):
        if(A % 100 == 0):
            cnt += 1
        A /= 100
    if(cnt == D):
        count +=1
    if(count == N):
        print(K)
        break
    K += 1

### FIXED CODE ###

D,N = map(int,input().split())
ans = (100**D) * N
if(N == 100):
    ans +=  100**D
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
maxfigure = sorted(A)[-1]
B = 0
for i in range(maxfigure):
    if A.count(i)%2 == 1:
        B += 1
print(B)

### FIXED CODE ###

N = int(input())
list = set()
for i in range(N):
    i = int(input())
    if i not in list:
        list.add(i)
    elif i in list:
        list.remove(i)
print(len(list))
### BUGGY CODE ###

import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
def main():
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
		
def sub():
	V = [list(map(int,inputs().split())) for p in [0]*N]
	M = [int(inputs()) for p in [0]*Q]
	V.sort(key = lambda x:(x[2],x[0],x[1]))
	for v in V:
		v[0] -= v[2]
		v[1] -= v[2] + 1
	for m in M:
		for n in range(N):
			if V[n][0] <=m and m <= V[n][1]:
				print(V[n][2])
				break
		else:
			print(-1)


if N>170000:
	sub()
else:
	main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

Q=input()
S="B"+input()+"B"
Q_num = Q.split(" ")[1]
query = []
for q in range(int(Q_num)):
  qu = input().split(" ")
  print(len(S[int(qu[0]):(int(qu[1])+1)].split("AC"))-1)

### FIXED CODE ###

Q=input()
S=input()
N,Q_num = int(Q.split(" ")[0]),int(Q.split(" ")[1])
AC=[0]
count = 0
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count = 1+count
  AC.append(count)
for q in range(int(Q_num)):
  qu = input().split(" ")
  print(AC[int(qu[1])-1]-AC[int(qu[0])-1])
### BUGGY CODE ###

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

d = []

bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append([b,c])

bc = sorted(bc,key=lambda x:x[1])

for elm in bc:
    for i in range(elm[0]):
        d.append(elm[1])

d.sort()
d.reverse()

#print(a)
#print(d)

sum = 0
ln = len(d)
for i in range(n):
    if i < ln:
        if a[i] < d[i]:
            sum += d[i]
        else:
            sum += a[i]
    else:
        sum += a[i]

print(sum)

### FIXED CODE ###

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

d = []

bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append([b,c])

bc = sorted(bc,key=lambda x:x[1],reverse=True)

for elm in bc:
    for i in range(elm[0]):
        d.append(elm[1])
        if len(d) >= n:
            break
    if len(d) >= n:
        break

d.sort()
d.reverse()

#print(a)
#print(d)

sum = 0
ln = len(d)
for i in range(n):
    if i < ln:
        if a[i] < d[i]:
            sum += d[i]
        else:
            sum += a[i]
    else:
        sum += a[i]

print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])
 
cnt = 0
B = []
for i in range(M):
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]

for i in range(min(N, len(B))):
    A[i] = max(A[i], B[i])
    
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])
C = sorted([[int(i) for i in input().split()] for i in range(M)], reverse = True, 
           key = lambda x: x[1])

cnt = 0
B = []
for i in range(M):
    if cnt > N:
        break
    B += [C[i][1]] * C[i][0]
    cnt += C[i][0]
    
B.sort(reverse = True)

x = min(N, len(B))

for i in range(x):
    A[i] = max(A[i], B[i])
    
print(sum(A))
### BUGGY CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

    for i in range(c3+1):
        for j in range(N+1):
            for k in range(N+1):
                if i>0 and j<N:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<N:
                    dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
                if k>0:
                    dp[i][j][k]+=(k/N)*dp[i][j][k-1]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()



### FIXED CODE ###

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

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for j in range(n):
        b[max(j-a[j], 0)] +=1
        if j+a[j] <n:
            b[j+a[j]+1] -=1
    for j in range(1,n):
        b[j] += b[j-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for j in range(n):
        b[max(j-a[j], 0)] +=1
        if j+a[j] <n:
            b[j+a[j]+1] -=1
    for j in range(1,n):
        b[j] += b[j-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )
### BUGGY CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
money=0
l=[]
for i in range(N):
    l.append(ab[i][0])
while True:
    min_id=l.index(min(l))
    for i in range(ab[min_id][1]):
        money+=l[min_id]
        ct+=1
        if ct==M:
            break
    ab[min_id][0]=-1
    l[min_id]=10000000000
    if ct==M:
        break
print(money)


### FIXED CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
ct1=0
ct2=0
money=0
l=[]
id=[]
for i in range(N):
    l.append(ab[i][0])
id=sorted(range(len(l)),key=lambda k: l[k])
l.sort()
while ct<M:
    while ct2<ab[id[ct1]][1]:##
        money+=l[ct1] #l[ct1]
        #print(money,l[ct1])
        ct+=1
        ct2+=1
        if ct==M:
            break
    ct1+=1
    ct2=0
print(money)
### BUGGY CODE ###

n, q = map(int,input().split())
s = input()
for i in range(q):
    ans = 0
    l, r = map(int,input().split())
    print(s[:r].count("AC")-s[:l].count("AC"))


### FIXED CODE ###

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

S=input()
Q=int(input())

flag=0
for i in range(Q):
    #query[i]=input()
    b=input()

    if(len(b)==1):
        #S=S[::-1]
        flag+=1
    else:
        a=b.split(" ")
        if(flag==0):
            if(a[1]=="1"):
                S=a[2]+S
            else:
                S+=a[2]
        else:
            if(a[1]=="2"):
                S=a[2]+S
            else:
                S+=a[2]
                
    flag=flag%2

if(flag==1):
    S=S[::-1]
print(S)



### FIXED CODE ###

S=input()
Q=int(input())

flag=0
forward=""
back=""
for i in range(Q):
    #query[i]=input()
    b=input()

    if(len(b)==1):
        #S=S[::-1]
        flag+=1
    else:
        a=b.split(" ")
        if(flag==0):
            if(a[1]=="1"):
                #S=a[2]+S
                forward=a[2]+forward
            else:
                #S+=a[2]
                back=back+a[2]
        else:
            if(a[1]=="1"):
                #S=a[2]+S
                back=back+a[2]
            else:
                #S+=a[2]
                forward=a[2]+forward
                
    flag=flag%2

S=forward+S+back
if(flag==1):
    S=S[::-1]
print(S)
### BUGGY CODE ###

n = int(input())
print(0)
s_st = input()
i_st = 0
if s=='Vacant': exit()
print(n-1)
s_en = input()
i_en = n-1
if s=='Vacant': exit()
for _ in range(20)
    print((i_st+i_en)//2)
    s_md = input()
    if s_md=='Vacant': exit()
    if (n-1)//2%2==0 and s_st!=s_md:
        i_en = (i_st+i_en)//2
    else:
        i_st = (i_st+i_en)//2
        s_st = s_md

### FIXED CODE ###

import sys
def valid():
    s = input()
    if s=='Vacant':
        sys.exit()
    return 1 if s=='Male' else 0

n = int(input())
print(0, flush=True)
s_l = valid()
lidx = 0
ridx = n

while True:
    midx = (lidx+ridx)//2
    print(midx, flush=True)
    s_m = valid()
    if ((midx-lidx)%2==1) ^ (s_l==s_m):
        lidx = midx
        s_l = s_m
    else:
        ridx = midx
### BUGGY CODE ###

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

for i in range(K):
  if A > 0:
    A = A - 1
  elif B > 0:
    B = B - 1
print(str(A) + ' ' + str(B))

### FIXED CODE ###

A, B, K = map(int,input().split())
a = 0
b = 0

if K <= A:
  a = A - K
  b = B
elif A < K <= A + B:
  b = B + A - K

print(str(a) + ' ' + str(b))
### BUGGY CODE ###

import numpy as np
n=int(input())
l=list(map(int,input().split()))
l.sort()
L=np.array(l)
cnt=0
for i in range(n-2):
  for j in range(i+1,n-1):
    cnt+=np.count_nonzero(L[j+1:]<L[i]+L[j])
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left

def main():
    n=int(input())
    l=sorted(list(map(int,input().split())))
    ans=0
    for i in range(n-2):
        a=l[i]
        for j in range(i+1,n-1):
            ans+=bisect_left(l,a+l[j])-j-1
    print(ans)

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

p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    for j in range(p):
      ans[-j-1] -= ((-1)**j)*cmb(p-1,j)*pow(i,j,p)
      ans[-j-1] %= mod
print(*ans)

### FIXED CODE ###

p = int(input())
a = list(map(int,input().split()))
mod = p
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def inv(x):
  return pow(x,mod-2,mod)
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
ans = [0]*p
for i in range(p):
  if a[i]:
    ans[0] += 1
    const = 1
    for j in range(p):
      ans[-j-1] -= ((-1)**(j%2))*cmb(p-1,j)*const
      ans[-j-1] %= mod
      const *= i
      const %= mod
print(*ans)
### BUGGY CODE ###

n, p = [int(i) for i in input().split()]
s = input()
ans = 0
pp = 0

for i in range(n):
    for j in range(i,n):
#         print(s[j])
        if i == j:
            pp = int(s[j])%p
        else:
            pp = (pp*10 + int(s[j]))%p
        if pp == 0:
            ans += 1
print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
s = [int(i) for i in list(input())][::-1]
summ  = 0
ans = 0
cnt = [0]*p # あまりの部屋
cnt[0] = 1
for i in range(n):
    d = s[i]*pow(10, i ,p)
    summ = (summ + d) %p
    cnt[summ] +=1

if p in [2,5]: # 10の因数は別処理
    if p == 2:
        ok_list = [0,2,4,6,8]
    if p == 5:
        ok_list = [0,5]
    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n-i
else: # 他のは,あまりが同じものは差し引けばあまりが0になるのでpで割り切れる判定
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1)//2 # nC2の計算

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

a, b, k = map(int, input().split())
l=[a,b]
for l in range(k-1):
  if a>0:
    a=a-1
  if a==0 and b>0:
    b=b-1
print(str(a)+" "+str(b))

### FIXED CODE ###

a, b, k = map(int, input().split())
if k <= a:
  print(a-k,b)
elif k-a<=b:
  b=b-(k-a)
  print(0,b)
else:
  print(0,0)
### BUGGY CODE ###

class Dictionary:
    def __init__(self):
        self.dic = []
    def insert(self, key):
        if not self.find(key):
            self.dic.append(key)
    def find(self, key):
        return key in self.dic

dic = Dictionary()
n = int(input())
for i in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
        dic.insert(cmd[1])
    elif cmd[0] == "find":
        if dic.find(cmd[1]):
            print("yes")
        else:
            print("no")
    else:
        print("wrong command")


### FIXED CODE ###

dic = set()
n = int(input())
for i in range(n):
    cmd, val = input().split()
    if cmd == "insert":
        dic.add(val)
    elif cmd == "find":
        print("yes" if val in dic else "no")
    else:
        print("wrong command")
### BUGGY CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
S=input()
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    num=(num+pow(10,i)*int(S[N-1-i]))%2019
    amari[i+1]=num
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)

#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)

### FIXED CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)
### BUGGY CODE ###

# 実行時間超過

N = int(input())
s_list=[]

for i in range(N):
    s_list.append(sorted(list(input())))

count=0
for i in range(N):
    for j in range(i+1,N):
        if s_list[i]==s_list[j]:
            count+=1
print(count)

### FIXED CODE ###

N = int(input())
s_list=[]
s_dict={}
count=0

for i in range(N):
    s = "".join(sorted(input()))
    if s not in s_dict:
        s_dict[s]=0
    else:
        s_dict[s]+=1
        count+=s_dict[s]
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1):
        for j in range(i+1, n):
           ans += (a[i]*a[j])%mod
    print(ans%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

input = sys.stdin.readline

def main():
    ans = 0
    mod = (10**9)+7
    n = int(input())
    a = list(map(int, input().split()))
    suma = sum(a)
    for i in range(n-1):
        suma -= a[i]
        ans += a[i]*suma
    print(ans%mod)

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

K,S = map(int,input().split())

count = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            s = x + y + z
            if s == S:
                count = count + 1    
print(str(count))

### FIXED CODE ###

K,S = map(int,input().split())

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >=0 and z <= K:
            count +=1
            
print(count)
### BUGGY CODE ###

from itertools import count

N, K = map(int, input().split())
As = [int(n) for n in input().split()]

visited = []
now = 0
num = 0
idx = 0
for i in count():
    if now in visited:
        idx = visited.index(now)
        num = len(visited) - idx
        break
    visited.append(now)
    now = As[now] - 1

if K <= idx:
    print(visited[K] + 1)
else:
    print(visited[idx + (K - idx) % num] + 1)

### FIXED CODE ###

from itertools import count

N, K = map(int, input().split())
As = [int(n) for n in input().split()]

visited = []
visited_set = set()
now = 0
num = 0
idx = 0
for i in count():
    if now in visited_set:
        idx = visited.index(now)
        num = len(visited) - idx
        break
    visited_set.add(now)
    visited.append(now)
    now = As[now] - 1

if K <= idx:
    print(visited[K] + 1)
else:
    print(visited[idx + (K - idx) % num] + 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

x = 2019
S = input()
l = len(S)

a, b = [],[0]
s = ''
for i in range(l):
#    a.append(int(S[:i+1]) % x)
#    if S[i] != '0':
    s = S[-i-1] + s
    b.append(int(s) % x)

ans = 0

xx = [0 for _ in range(2019)]
for i in range(len(b)):
    xx[b[i]] += 1

def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 2019

S = input()
l = len(S)
#S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod
#    b.append(s % x)
    xx[s] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)