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

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[1000000]*n    

que=[]
que.append(0)
while(len(que)):
    v=que.pop(0)
    for i in to[v]:
        if(dist[i] is 1000000):
            dist[i]=v+1
            que.append(i)
        
print("Yes")
for i in dist[1:]:
    print(i)    


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
x1 = []
for i, xi in enumerate(x):
    x1.append([i, xi])

x_sort = sorted(x1, key=lambda x: x[1])
t = int(n / 2)
lxt = []
for i in range(n):
    if i < t:
        lxt.append(x_sort[i][0])
    else:
        break

for i in range(n):
    if i in lxt:
        print(x_sort[t][1])
    else:
        print(x_sort[t - 1][1])


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
x1 = []
for i, xi in enumerate(x):
    x1.append([i, xi])

x_sort = sorted(x1, key=lambda x: x[1])
t = int(n / 2)
lxt = []
for i in range(n):
    if i < t:
        x[x_sort[i][0]] = x_sort[t][1]
    else:
        x[x_sort[i][0]] = x_sort[t - 1][1]

for i in range(n):
    print(x[i])
### BUGGY CODE ###

k=int(input())

now=7
for i in range(k+10):
	if now%k==0:
		print(i+1)
		exit()
	now*=10
	now+=7
print(-1)
    

### FIXED CODE ###

k=int(input())

now=7%k
for i in range(k+10):
	if now==0:
		print(i+1)
		exit()
	now*=10
	now+=7
	now%=k
print(-1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def score(i,x,y,turn):
        if i==n-1:
            return abs(x-y)
        if (i,x,y,turn) in memo:
            return memo[(i,x,y,turn)]
        if turn:
            res=0
            for j in range(i+1,n):
                res=max(res,score(j,aa[j],y,not turn))
        else:
            res=10**16
            for j in range(i+1,n):
                res=min(res,score(j,x,aa[j],not turn))
        memo[(i,x,y,turn)]=res
        return res

    n,z,w=map(int, input().split())
    aa=list(map(int, input().split()))
    memo={}
    print(score(-1,z,w,True))

main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def MI(): return map(int, sys.stdin.readline().split())

def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, z, w = MI()
    aa = LI()
    if n - 2 >= 0:
        print(max(abs(aa[n - 1] - aa[n - 2]), abs(aa[n - 1] - w)))
    else:
        print(abs(aa[n - 1] - w))

main()
### BUGGY CODE ###

n = input()
n = int(n)

l = list(map(int, input().split()))

i = 1

while i <= n :
    num = l.count(i)
    print(num)
    i += 1

### FIXED CODE ###

def main():
  N = int(input())
  A = [0] * N 
  for i in input().split():
    A[int(i)-1] += 1 
  for i in range(N):
    print(A[i])

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

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

n = input()
class DoubleLinkedList(object):
    def __init__(self):
        pass
        
    def insert(self, value):
        new = DoubleLinkedList()
        new.next = self.next
        new.prev = self
        self.next.prev = new
        self.next = new
        new.value = value
        
    def delete(self):
        next = self.next
        prev = self.prev
        self.next.prev = prev
        self.prev.next = next

head = DoubleLinkedList()
tail = DoubleLinkedList()
head.next = tail
tail.prev = head

for i in xrange(n):
    command = raw_input().split()
    if command[0] == "insert":
        head.insert(int(command[1]))
    elif command[0] == "delete":
        key = int(command[1])
        e = head.next
        while True:
            if e is tail:
                break
            if e.value == key:
                e.delete()
                break
            e = e.next
    elif command[0] == "deleteFirst":
        if not head.next is tail:
            head.next.delete()
    elif command[0] == "deleteLast":  
        if not tail.prev is head:
            tail.prev.delete()
    
e = head.next
while True:
    if e is tail:
        break
    print e.value,
    e = e.next

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = input()
l = []
tail = 0
for i in xrange(n):
    cmd = raw_input().split()
    if cmd[0] == "insert":
        l.append(cmd[1])
    elif cmd[0] == "delete":
        try:
            l.pop(len(l) - l[::-1].index(cmd[1]) -1)
        except ValueError:
            pass
    elif cmd[0] == "deleteFirst":
        l.pop()
    elif cmd[0] == "deleteLast":
        tail += 1

print " ".join(l[tail:][::-1])
### BUGGY CODE ###

n = int(input())
m = list(map(int, input().split()))
list_number = []
for i in range(1,n+1):
    list_number.append(m.count(i))
for i in list_number:
    print(i)

### FIXED CODE ###

n = int(input())
a = [0] * n
m = list(map(int, input().split()))
for i in m:
    a[i-1] += 1
for i in a:
    print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    b = []
    for i, val in enumerate(A):
        b.append(val)
        b = b[::-1]
        #print(*b)
    
    print(*b)
    
        
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    b = [0 for _ in range(N)]
    base = (N//2)
    cnt = 1
    
    flg = False
    if N % 2 == 0:
        flg = True
    
    for i, val in enumerate(A):
        
        if flg == True:
            if i == 0:
                b[base] = val
            elif i % 2 == 1:
                b[base-cnt] = val
            else:
                b[base+cnt] = val
                cnt+=1
        else:
            if i == 0:
                b[base] = val
            elif i % 2 == 1:
                b[base+cnt] = val
            else:
                b[base-cnt] = val
                cnt+=1
    
    print(*b)
    
        
if __name__ == "__main__":
	main()
### BUGGY CODE ###

#coding=utf-8
from itertools import combinations
from collections import Counter

def solve(n, ss):
    filtered_ss = list(filter(lambda x: x in "MARCH", map(lambda x:x[0], ss)))

    gc = Counter(filtered_ss)
    if len(gc) < 3:
        return 0

    ans = 0
    for permutation in combinations("MARCH", 3):
        if permutation[0] in gc.keys() and permutation[1] in gc.keys() and permutation[2] in gc.keys():
            tmp = (gc[permutation[0]] * gc[permutation[1]] * gc[permutation[2]])
            ans = ans + tmp

    return ans

def main():
    n = int(input())
    ss = []
    for x in range(n):
        ss = ss + [input()]
    print(solve(n, ss))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding=utf-8
from itertools import combinations
from collections import Counter

def solve(n, gc):
    #filtered_ss = list(filter(lambda x: x in "MARCH", ss))

    #gc = Counter(filtered_ss)
    if len(gc) < 3:
        return 0

    ans = 0
    for permutation in combinations("MARCH", 3):
        ans += (gc[permutation[0]] * gc[permutation[1]] * gc[permutation[2]])

    return ans

def main():
    n = int(input())
    gc = {'M': 0, 'A': 0, 'R': 0, 'C': 0, 'H': 0}
    for _ in range(n):
        x = input()[0]
        if x in "MARCH":
            gc[x] += 1
    print(solve(n, gc))

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

A, B, C, D = map(int, input().split())
mod = 998244353

dp = [[0]*(D+2) for i in range(C+2)]
dp[A][B] = 1
for i in range(A, C+1):
    for j in range(B, D+1):
        if i-A == j-B == 1:
            dp[i][j] -= (i-1)*(j-1)
        else:
            dp[i][j] -= dp[i-1][j-1]*(j-1)*(i-1)
        dp[i][j] %= mod
        dp[i+1][j] += dp[i][j] * j
        dp[i][j+1] += dp[i][j] * i

print(dp[-2][-2])


### FIXED CODE ###

def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            ret = 0
            if i == 0 and j == 0:
                continue
            if i > 0 and j > 0:
                if i == j == 1:
                    ret -= (A+i-1) * (B+j-1)
                else:
                    ret -= dp[i-1][j-1]
                    ret *= (A+i-1)*(B+j-1)
            ret += dp[i-1][j]*(B+j) + dp[i][j-1]*(A+i)

            ret %= mod
            dp[i][j] = ret
    print(dp[c][d])


main()
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for j in range(1,n-1):
    for i in range(j):
        for k in range(j+1,n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j - i != k - j:
                ans += 1
print(ans)

### FIXED CODE ###

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

n,k = map(int, input().split())
a = list(map(int, input().split()))
t=1
for i in a[:k]:
  t *= i
temp = [t]

for index, i in enumerate(a[k:]):
  temp.append(temp[-1] * i // a[index])
  
for i,j in zip(temp, temp[1:]):
  if i < j:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

for i in range(k, n):
  if a[i] > a[i-k]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import bisect
def main():
    N,D,A=map(int,input().split())
    XH=[list(map(int,input().split())) for _ in range(N)]
    XH.sort()
    for i in range(N):
        XH[i][1]=-(-XH[i][1]//A)
    X=[x for x,a in XH]
    far=[0]*N
    for i in range(N):
        far[i]=bisect.bisect_right(X,X[i]+2*D)-1

    ans=0
    for i in range(N):
        x=XH[i][0]
        hp=XH[i][1]
        if hp<=0:
            continue
        #XH=[[xx,hh-hp] for xx,hh in XH[:far[i]+1]]+XH[far[i]+1:]
        for j in range(i,far[i]+1):
            XH[j][1]-=hp
        ans+=hp
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
def main():
    N,D,A=map(int,input().split())
    XH=[list(map(int,input().split())) for _ in range(N)]
    XH.sort()
    for i in range(N):
        XH[i][1]=-(-XH[i][1]//A)
    X=[x for x,a in XH]
    far=[0]*N
    for i in range(N):
        far[i]=bisect.bisect_right(X,X[i]+2*D)-1

    ans=0
    carry=0
    outrange=[0]*(N+1)
    for i in range(N):
        x=XH[i][0]
        hp=XH[i][1]
        carry-=outrange[i]
        if carry>=hp:
            continue
        outrange[bisect.bisect_right(X,X[i]+2*D)]+=hp-carry
        ans+=hp-carry
        carry+=hp-carry
    print(ans)

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

a=1
for i in range(1,int(input())+1):
  a*=i
print(a%(10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

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

# A[i]は問題では1から始まるので注意
# A[i], A[j]について、|j-i| == A[j]+A[i]なら極秘情報の取引をする
# この条件を満たすペアの数
# modはとらなくてよいぐらい
# i, jは2*10^5の程度だから全件で10^10の程度, A[i]は10^9の程度
# j > iとして良い。j-iの値を固定して計算はできる。
# いったんこれぐらいで始めてみよう

# だめだった
# 値の範囲で搾ろう。

counter = 0
for i in range(N):
    bi = i+A[i]
    for j in range(i+1, N):
        if j-A[j] == bi:
            counter += 1
print(counter)


### FIXED CODE ###

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

# 線形で計算できる
# j > iとしてA[j]+A[i] = j-iよりA[i]+i=j-A[j]
# iとjを分離できたのでjを前に進めていって、計算結果を貯めていけばいい
# 

counter = 0
dic = {}
for j in range(N):
    if j-A[j] in dic:
        counter += dic[j - A[j]]
    if j + A[j] in dic:
        dic[j+A[j]] += 1
    else:
        dic[j+A[j]] = 1
print(counter)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(m):
    b, c = map(int, input().split())
    C = [c]*b
    A.extend(C)

A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B=[list(map(int, input().split())) for _ in range(Q)]

ans=[]

for i in B:
  b=i[0]
  c=i[1]
  A=[i if i!=b else c for i in A ]
  
  ans.append(sum(A))
  
for i in ans:
  print(i)
  


### FIXED CODE ###

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

num=[0]*10**5 
a=sum(A)

for i in A: #各数字が何個あるか
  num[i-1]+=1

for _ in range(Q):
  b,c=map(int, input().split())
  
  a=a+(-num[b-1]*b+c*num[b-1])
  num[c-1]+=num[b-1]
  num[b-1]-=num[b-1]
  print(a)
### BUGGY CODE ###

K , S = map(int,input().split())
k = 0
for i in range(K+1):
  for j in range(K+1):
    for l in range(K+1):
      if i + j + l == S:
        k += 1
print(k)        

### FIXED CODE ###

K , S = map(int,input().split())
k = 0
for i in range(K+1):
  for j in range(min([S-i+1,K+1])):
    if 0 <= S - i - j <= K:
      k += 1
print(k)
### BUGGY CODE ###

N,M=map(int,input().split())
E=[(1,N)]
for _ in[0]*M:
    a,b=map(int,input().split())
    E+=[(a,b)]
    F=[]
    for s,t in E:
        if s<=a and b<=t:
            F+=[(a,b)]
        else:
            F+=[(s,t)]
    E=F
cnt=0
while E:
    cnt+=1
    M, Mi = 0, 0
    A = [0]*N
    l = len(E)
    B = [set(range(l))for _ in[0]*N]
    for k,(s,t) in enumerate(E):
        for i in range(s,t):
            A[i]+=1
            B[i]-={k}
            if M<A[i]:
                M, Mi = A[i], i
    E=[E[i]for i in B[Mi]]
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
ab=sorted([list(map(int,input().split()))for _ in[0]*m],key=lambda x:x[1])
cnt=0
x=0
for a,b in ab:
   if x<a:x=b-1;cnt+=1
print(cnt)
### BUGGY CODE ###

N = int(input())

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

a = 0
while a < N:  
  B = [elem for idx,elem in enumerate(A) if idx != a]
  B.sort()
  a += 1
  print(B[(N-1)//2])

### FIXED CODE ###

from sys import stdin
 
N = int(stdin.readline().rstrip())
 
A = [int(x) for x in stdin.readline().rstrip().split()]

B = sorted(A)
 
for i in range(N):  
  if A[i] < B[N//2]:
    print(B[N//2])
  else:
    print(B[N//2-1])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        B, C = map(int,input().split())
        for j in range(B):
            tmp = heapq.heappushpop(q, C)
            total += (C - tmp)
            if tmp == C:
                break

    print(total)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M = map(int,input().split())
    q = list(map(int, input().split()))
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda x:-x[1])
    total = sum(q)
    heapq.heapify(q)

    for i in range(M):
        for j in range(X[i][0]):
            tmp = heapq.heappushpop(q, X[i][1])
            if tmp < X[i][1]:
                total += (X[i][1] - tmp)
            else:
                break

    print(total)

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

N = int(input())
count=0
for i in range(N):
    I=i+1
    Istr = str(I)
    if Istr.count("3")>0 and Istr.count("5")>0 and Istr.count("7"):
        if Istr.count("0") == 0 and Istr.count("1") == 0 and Istr.count("2") == 0 and Istr.count("4")==0 and Istr.count("6")==0 and Istr.count("8")==0 and Istr.count("9")==0:
            count+=1
        else:
            pass
print(count)

### FIXED CODE ###

N = int(input())
def shichi(n):
    if int(n) > N:
        return 0
    ret=1 if all(n.count(c)>0 for c in "753") else 0
    for c in "753":
        ret += shichi(n+c)
    return ret
print(shichi("0"))
### BUGGY CODE ###

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

if K == 1:
    print(0)
    exit()

A_List.sort()

def cmb(n, r):
    return fact(n) // fact(n - r) // fact(r) if n > 0 and r > 0 else 1

factList = [-1]*N
factList[0]=1
for i in range(1,N):
    factList[i]=factList[i-1]*i

def fact(n):
    return factList[n]

ans = 0

for under in range(N):
    for top in range(under,N):
        if top - under + 1 < K:
            continue
        fx = A_List[top] - A_List[under]
        ans += fx * cmb(top-under-1 , K-2)

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




### FIXED CODE ###

SIZE=10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD
 
def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
 
def chofuku(ball,box): # nHk mod MOD の計算
    return choose(box+ball-1,box)


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

smax=0
smin=0
for i in range(N):
    smax+=A[i]*choose(i,K-1)
    smax%=MOD
    smin+=A[i]*choose(N-i-1,K-1)
    smin%=MOD

print((smax-smin)%MOD)
### BUGGY CODE ###

class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x

from operator import or_

N = int(input())
S = [set(i) for i in input()]

tree = SegTree(N, e=set(), operator_func=or_)
tree.set_list(S)

Q = int(input())
for _ in range(Q):
    mode, i, v = input().split()
    if mode=="1":
        i = int(i)-1
        tree.update(i, set(v))
    else:
        i = int(i)-1
        v = int(v)
        print(len(tree.get(i, v)))

### FIXED CODE ###

import sys
from operator import or_
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def main():
    N = int(input())
    S = list(input())[:-1]
    trees = {chr(97+i):SegTree(N, e=False, operator_func=or_) for i in range(26)}

    for i, s in enumerate(S):
        trees[s].update(i, True)

    Q = int(input())
    for _ in range(Q):
        mode, i, v = input().split()
        if mode=="1":
            i = int(i)-1
            trees[S[i]].update(i, False)
            trees[v].update(i, True)
            S[i] = v
        else:
            i = int(i)-1
            v = int(v)
            ans = 0
            for j in range(26):
                ans += trees[chr(97+j)].get(i, v)
            print(ans)


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

S = input()

mods = [0]*2019
result = 0

for i in range(len(S)+1):
  x = int(S[len(S)-i: len(S)])%2019 if i>0 else 0
  result += mods[x]
  mods[x] += 1

print(result)

### FIXED CODE ###

S = input()[::-1]

modCount = [0]*2019
modCount[0] = 1
mod = 0
dig = 1
result = 0

for i in range(len(S)):
  mod = (int(S[i:i+1])*dig+mod)%2019
  dig = (dig*10)%2019
  result += modCount[mod]
  modCount[mod] += 1

print(result)
### BUGGY CODE ###

a=int(input())
b=int((a-1)*a/2)
c=[]
c.append(b)
for i in range(1,int(a/2)):
    if i<a%(i+1):
        c.append(b+(a%(i+1)-i))
print(max(c))

### FIXED CODE ###

a=int(input())
print(a*(a-1)//2)
### BUGGY CODE ###

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

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if (i + j + k) == S:
                c += 1

print(c)


### FIXED CODE ###

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

for i in range(K+1):
    for j in range(K+1):
            if 0<=(S-i-j)<=K:
                c += 1

print(c)