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

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]*N# iに到達するときの最大得点
moji=[1]+[0]*(N-1)#infなら0をかえす
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if moji[b[m]-1]:
        V[b[m]-1]=max(V[b[m]-1],V[a[m]-1]+c[m])
      else:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji[b[m]-1]=1
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if moji[a[m]-1]:#共に有限の時はやる
      if V[a[m]-1]+c[m]>V[b[m]-1]:
        V[b[m]-1]=V[a[m]-1]+c[m]
        moji2[b[m]-1]=1
    if moji2[a[m]-1]:
      moji2[b[m]-1]=1
if moji2[N-1]:
  print("inf")
else:
  print(V[N-1])

### FIXED CODE ###

import sys
N,M=map(int, input().split())
a=[]
b=[]
c=[]
for m in range (0,M):
  A,B,C=map(int, input().split() )
  a+=[A]
  b+=[B]
  c+=[C]
V=[0]+[-10**12]*(N-1)# iに到達するときの最大得点
 
for n in range(N-1):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
 
moji2=[0]*N
for n in range(N):
  for m in range(M):
    u=a[m]
    v=b[m]
    if V[b[m]-1]<V[a[m]-1]+c[m]:#共に有限の時はやる
      V[b[m]-1]=V[a[m]-1]+c[m]
      moji2[b[m]-1]=1
      if moji2[N-1]:
        print("inf")
        sys.exit()
print(V[N-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cnt = 0
a_set = set(a)
for i in a_set:
    if a.count(i) % 2 != 0:
        cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
D = {}
cnt = 0
for _ in range(n):
    a = int(input())
    if a not in D:
        D[a] = 1
    else:
        D[a] += 1
for i in D:
    if D[i] % 2 != 0:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
for _ in range(Q):
  l, r = map(int, input().split())
  print(len(re.findall('AC', S[l - 1:r])))


### FIXED CODE ###

from itertools import accumulate
from operator import add

N, Q = map(int, input().split())
S = input()
idx_list = [1 if S[i:i + 2] == 'AC' else 0 for i in range(len(S) - 1)]
idx_list_cumsum = [0] + list(accumulate(idx_list, add))

for _ in range(Q):
  l, r = map(int, input().split())
  print(idx_list_cumsum[r - 1] - idx_list_cumsum[l - 1])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)

def list_euclid(int_list):
    ans = int_list[0]
    if len(int_list) == 1:
        return ans
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_gcd = 0
b_int = 0
min = 1
if n == 2:
    max_gcd = max(a)
elif n < 5:
    for i in range(0, n):
        if b_int == a[0]:
            p = a.pop(0)
            a.append(p)
        else:
            p = a.pop(0)
            b_int = p
            x = list_euclid(a)
            if max_gcd < x:
                max_gcd = x
            a.append(p)
else:
    for i in range(0, n):
        if b_int == a[0]:
            p = a.pop(0)
            # a.append(p)
        else:
            if max_gcd == 0:
                p = a.pop(0)
                b_int = p
                k = len(a) // 2
                x = 0
                y = list_euclid(a[0:k])
                if y == 1:
                    x = 1
                else:
                    z = list_euclid(a[k:len(a)])
                    x = euclid(y, z)
                if max_gcd < x:
                    max_gcd = x
                a.append(p)
                min = p
            elif min <= max_gcd:
                break
            else:
                p = a.pop(0)
                b_int = p
                k = len(a) // 2
                x = 0
                if k < 2:
                    x = list_euclid(a)
                else:
                    y = list_euclid(a[0:k])
                    if y == 1:
                        x = 1
                    else:
                        z = list_euclid(a[k:len(a)])
                        x = euclid(y, z)
                if max_gcd < x:
                    max_gcd = x
                a.append(p)
print(max_gcd)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

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

for i in range(K, N):
    tmp1 = 1
    tmp2 = 1
    for j in range(i-K, i):
        tmp1 *= A[j]
        tmp2 *= A[j+1]
    if tmp1 < tmp2:
        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-K] < A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from functools import lru_cache

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))


@lru_cache(None)
def dfs(d,h,pre):
    if d == N - 1:
        return h
    tmp = [0] 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,h + a,idx)
            tmp.append(res)
    return max(tmp)

import sys
sys.setrecursionlimit(2147483647)

print(dfs(-1,0,-1))

### FIXED CODE ###

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))

dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j]= A[i][j]
        else:
            tmp = [0] 
            for k in range(3):
                if j !=k:
                    tmp.append(dp[i-1][k])
            dp[i][j] = max(tmp) + A[i][j]
print(max(dp[-1]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
a = 0
while N != 0:
    a += N % 10
    N = N //10
if a%9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = list(input())[:-1]
n = len(N)
b = 0
for i in range(n):
    s = N[i]
    a = int(s)
    b += a
    b %= 9
if b % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())

A=[i for i in range(10**7+1)]
B=[i for i in range(10**7+1)]

if N==1:
    print(1)
    sys.exit()

def main():
    ANS=0

    for i in range(2,N+1):
        if B[i]==1:
            ANS+=A[i]
            continue
        
        for j in range(i,10**7+1,i):

            count=0
            while B[j]%i==0:
                count+=1
                B[j]//=i
            A[j]*=count+1
        ANS+=A[i]

    print(ANS+1)
main()

### FIXED CODE ###

def main(): 
    N=int(input())
    ANS=0
    for i in range(1,N+1):
        ANS+=i*(N//i*(N//i+1)//2)
    print(ANS)
main()
### BUGGY CODE ###

N=int(input()) 
A=list(map(int,input().split()))
a=[]
for i in range(N):   
    if A[i] in a:
        print("NO")
        break

    else:
        a.append(A[i])
        if i==N-1:print('YES')

### FIXED CODE ###

N=int(input()) 
A=sorted(list(map(int,input().split())))
a=[]
for i in range(N-1):   
    if A[i]==A[i+1]:
        print("NO") 

        break
    elif i==N-2:print("YES")
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 0
i = 0
while i < n:
  new = p[0:i+1]
  if p[i] == min(new):
    c = c + 1
  i = i + 1
print(c)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
c = 0
i = 0
temp_min = p[i]
while i < n:
  if p[i] <= temp_min:
    c = c + 1
    temp_min = p[i]
  i = i + 1
print(c)
### BUGGY CODE ###

# coding: utf-8
n, k = map(int, input().split())
p =list(map(int,input().split()))
pm = 0
for i in range(len(p) - k + 1):
  tmp = 0
  for j in range(k):
    tmp += p[i+j]
  pm = tmp if (tmp >= pm) else pm
# print(pm)
ans = (pm + k) / 2
print(ans)

### FIXED CODE ###

# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
pm = pp = sum(p[0:k])
for i in range(n - k):
    pp = pp - p[i] + p[k+i]
    pm = pp if (pp >= pm) else pm
ans = (pm + k) / 2
print(ans)
### BUGGY CODE ###

N, T = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

items.sort()

ans = 0
dp = {0: 0}
for wi, vi in items:
    for w, v in dp.items():
        if w < T:
            v2 = v + vi
            if v2 > ans:
                ans = v2

    for w, v in list(dp.items()):
        w2 = w + wi
        if w2 <= T:
            v2 = v + vi
            if w2 in dp:
                if v2 > dp[w2]:
                    dp[w2] = v2
            else:
                dp[w2] = v2

v2 = max(dp.values())
ans = max(ans, v2)

print(ans)


### FIXED CODE ###

N, T = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

items.sort()

ans = 0
dp = {0: 0}
for wi, vi in items:
    for w, v in dp.items():
        if w < T:
            v2 = v + vi
            if v2 > ans:
                ans = v2

    for w, v in list(dp.items()):
        w2 = w + wi
        if w2 <= T:
            v2 = v + vi
            if w2 in dp:
                if v2 > dp[w2]:
                    dp[w2] = v2
            else:
                dp[w2] = v2

v2 = max(dp.values())
ans = max(ans, v2)

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

h,w = map(int, input().split())
g = []
for _ in range(h):
  g.append(input())
l = [[0 for i in range(w)] for j in range(h)]
r = [[0 for i in range(w)] for j in range(h)]
d = [[0 for i in range(w)] for j in range(h)]
u = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if g[i][j] == '#':
      l[i][j] = 0
      u[i][j] = 0
    else:
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1]+1
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j]+1
for i in reversed(range(h)):
  for j in reversed(range(w)):
    if g[i][j] == '#':
      r[i][j] = 0
      d[i][j] = 0
    else:
      if j == w-1:
        r[i][j] = 1
      else:
        r[i][j] = r[i][j+1]+1
      if i == h-1:
        d[i][j] = 1
      else:
        d[i][j] = d[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(l[i][j]+r[i][j]+u[i][j]+d[i][j]-3,ans)
print(ans)

### FIXED CODE ###

h,w = map(int, input().split())
g = []
for _ in range(h):
  g.append(input())
l = [[0 for i in range(w)] for j in range(h)]
r = [[0 for i in range(w)] for j in range(h)]
d = [[0 for i in range(w)] for j in range(h)]
u = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if g[i][j] == '#':
      l[i][j] = 0
      u[i][j] = 0
    else:
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1]+1
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j]+1
for i in reversed(range(h)):
  for j in reversed(range(w)):
    if g[i][j] == '#':
      r[i][j] = 0
      d[i][j] = 0
    else:
      if j == w-1:
        r[i][j] = 1
      else:
        r[i][j] = r[i][j+1]+1
      if i == h-1:
        d[i][j] = 1
      else:
        d[i][j] = d[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(l[i][j]+r[i][j]+u[i][j]+d[i][j]-3,ans)
print(ans)
### BUGGY CODE ###

import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
l=[i for i in range(N)]
ans=float("inf")
for v in itertools.combinations(l,2):
  xmax=max(XY[v[0]][0],XY[v[1]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
    
for v in itertools.combinations(l,3):
  xmax=max(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
    
for v in itertools.combinations(l,4):
  xmax=max(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
  xmin=min(XY[v[0]][0],XY[v[1]][0],XY[v[2]][0],XY[v[3]][0])
  ymax=max(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
  ymin=min(XY[v[0]][1],XY[v[1]][1],XY[v[2]][1],XY[v[3]][1])
  k=0
  for xy in XY:
    x,y=xy[0],xy[1]
    if xmin<=x and x<=xmax:
      if ymin<=y and y<=ymax:
        k+=1    
  if k>=K:
    ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)

### FIXED CODE ###

import itertools
N,K=map(int,input().split())
XY=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")

for xv in itertools.combinations( [xy[0] for xy in XY] ,2):
  for yv in itertools.combinations( [xy[1] for xy in XY] ,2):
    xmax=max(xv[0],xv[1])
    xmin=min(xv[0],xv[1])
    ymax=max(yv[0],yv[1])
    ymin=min(yv[0],yv[1])

    k=0
    for xy in XY:
      x,y=xy[0],xy[1]
      if xmin<=x and x<=xmax:
        if ymin<=y and y<=ymax:
          k+=1    
    if k>=K:
      ans=min(ans,(xmax-xmin)*(ymax-ymin))
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
a = list(map(int,input().split()))
q = int(input())
sum_a = 0
output = 0
cnt = 0
a.sort()

for i in range(q):
  bc = list(map(int,input().split()))
  flag = False
  try:
    nn = a.index(bc[0])
    for j in range(nn-1, len(a)):
      if a[j] == bc[0]:
        a[j] = bc[1]
        flag = True
      else:
        if flag == True:
          break
  except ValueError:
    pass
  print(sum(a))
  a.sort()


  
  

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
count = [0]*((10**5)+100)
for i in range(len(A)):
  count[A[i]] += 1
sumA = sum(A)
for q in range(Q):
  count[BC[q][1]] += count[BC[q][0]]
  sumA += (BC[q][1] - BC[q][0])*count[BC[q][0]]
  print(sumA)
  count[BC[q][0]] = 0
### BUGGY CODE ###

N, M = [int(n) for n in input().split()]
A = [1 for _ in range(N)]

for _ in range(M):
    L, R = [int(n) for n in input().split()]
    for i in range(0, L-1, 1):
        A[i] = 0
    for i in range(R, N, 1):
        A[i] = 0

cnt = 0
for i in range(N):
    if A[i] == 1:
        cnt += 1

print(cnt)


### FIXED CODE ###

N, M = [int(n) for n in input().split()]
left, right = 1, N

for _ in range(M):
    L, R = [int(n) for n in input().split()]
    if left < L:
        left = L
    if R < right:
        right = R

if left <= right:
    print(right - left + 1)
else:
    print(0)
### BUGGY CODE ###

if __name__ == '__main__':
	islands_count, demands_count = list(map(int, input().split()))
	demands = []
	bridges = [True for _ in range(islands_count - 1)]

	for i in range(demands_count):
		demand = list(map(int, input().split()))
		demands.append(demand)

	demands.sort(key=lambda x: x[1])

	for demand in demands:
		is_disconnected = False
		for bridge in range(demand[0] - 1, demand[1] - 1):
			if not bridges[bridge]:
				is_disconnected = True
				break
		if not is_disconnected:
			bridges[demand[1] - 2] = False
	print(bridges.count(False))


### FIXED CODE ###

if __name__ == '__main__':
    islands_count, demands_count = list(map(int, input().split()))
    demands = []
    break_count = 0

    for i in range(demands_count):
        demand = list(map(int, input().split()))
        demands.append(demand)

    demands.sort(key=lambda x: x[1])
    west_edge = 0

    for demand in demands:
        if demand[0] >= west_edge:
            break_count += 1
            west_edge = demand[1]

    print(break_count)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc110/tasks/abc110_d


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


def get_prime_dic(n):
    dic = {}

    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    return dic


# Calculate count of combination
def combinations_count(n, r):
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


d = get_prime_dic(M)
# print(d)

ans = 1

for k, v in d.items():
    ans *= combinations_count(v + N - 1, v)


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


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
def func(M):
  res = []
  i = 2
  while i * i <= M:
    c=0
    while M % i == 0:
      M /= i
      c += 1
    if c > 0:
      res.append(c)
    i += 1
  if M > 1:
    res.append(1)
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % mod
print(ans)
### BUGGY CODE ###

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

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            count += L_list[i] + L_list[j] > L_list[k]

print(count)

### FIXED CODE ###

import bisect

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

L_list = sorted(L_list)

total = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        total += bisect.bisect_left(L_list, L_list[i] + L_list[j]) - j -1

print(total)
### BUGGY CODE ###

N = int(input())
life = list(map(int, input().split()))
min = 1000000000000
while len(life) >1:
    life = list(set(life))
    for i in life:
        if i < min: min = i
    
    life_array=[]
    for i in life:
        if i%min != 0 and i not in life_array: life_array.append(i%min)
    life = [min] + life_array

print(life[0])

### FIXED CODE ###

N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array = [life[0]] + [i%life[0] for i in life if i%life[0] !=0]
    life = life_array
    #for i in life_array:
        #if i not in life:
            #life.append(i)
 
print(life[0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    visited = []
    add_visited = visited.append
    def dfs(root, point):
        point += counter[root]
        ans[root] = point
        add_visited(root)
        for j in tree[root]:
            if j in visited:
                continue
            dfs(j, point)
        return

    dfs(1, 0)
    for i in range(1, n + 1):
        print(ans[i], '', end='')
    return ans


m()


### FIXED CODE ###

import queue
import sys
def input(): return sys.stdin.readline().rstrip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    que = queue.Queue()
    visited = [False] * (n+1)

    def bfs(root, base):
        base += counter[root]
        visited[root] = True
        for e in tree[root]:
            if visited[e]:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited[x] = True
            for e in tree[x]:
                if visited[e]:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    print(*counter[1:])
    return


m()
### BUGGY CODE ###

from collections import defaultdict
n,W=list(map(int,input().split()))
li=[]
wr=[0]*n
vr=[0]*n
dd=defaultdict(lambda:0)
for i in range(n):
	w,v=map(int,input().split())
	wr[i]=w
	vr[i]=v
def maxv(i,w):
	if dd[(i,w)]!=0:
		return dd[(i,w)]
	if i==n:
		return 0
	if w+wr[i]>W:
		return maxv(i+1,w)
	a=vr[i]+maxv(i+1,w+wr[i])
	b=maxv(i+1,w)
	c=max(a,b)
	dd[(i,w)]=c
	return c
print(maxv(0,0))



### FIXED CODE ###

n,W=map(int,input().split())
dp=[0]*(W+1)
dd=dp.copy()
for i in range(n):
	w,v=map(int,input().split())
	for j in range(W):
		cw=j+w
		cv=dp[j]+v
		if cw <=W and dd[cw]<cv:
			dd[cw]=cv
	dp=dd.copy()
print(dp[W])
### BUGGY CODE ###

import numpy as np

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

l = np.array([0 for _ in range(n)])
start = 0

for i in range(n-1):
  if h[i] >= h[i+1]:
    l[start:i+1] += 1
  else:
    start = i+1
    
print(max(l))

### FIXED CODE ###

import numpy as np

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

l = np.array([0 for _ in range(n)])
start = 0
count = 0
for i in range(n-1):
  if h[i] >= h[i+1]:
    count += 1
  else:
    l[start:i] += count
    start = i+1
    count = 0
else:
  l[start:] += count

print(max(l))
### BUGGY CODE ###

def main():
    N = int(input())
    A, B = [], []
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        AB.append([a, b])

    AB.sort(key=lambda x: x[1])

    time = 0
    while (len(AB) > 0):
        flag = True
        a, b = AB[0]
        if time + a <= b:
            time += a
            AB.pop(0)
            flag = False
        if flag:
            break
    if len(AB) == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A, B = [], []
    AB = []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        AB.append([a, b])

    AB.sort(key=lambda x: x[1])

    time = 0
    count = 0
    for i in range(N):
        flag = True
        a, b = AB[i]
        if time + a <= b:
            time += a
            count += 1
            flag = False
        if flag:
            break

    if count == N:
        print('Yes')
    else:
        print('No')    

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

cnt=0
S=str(input())
mc=[0]*2019
L=len(S)

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mt=tg%2019
    if mt==0:cnt+=1
    cnt+=mc[mt]
    mc[mt]+=1
    digit*=10%2019
    
print(cnt)

### FIXED CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])