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

import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(zero))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    tot_zero = zero_acc[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
        tot_zero += zero_acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(zero))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    tot_zero = zero_acc[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
        tot_zero += zero_acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  buka=a.count(i)
  print(buka)

### FIXED CODE ###

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

def calculate(arr):
    arr2 = rank(arr.copy())

    max = arr2[len(arr2) - 1]
    second = arr2[len(arr2) - 2]

    for i in range(len(arr)):
        value = arr[i]
        if max != value:
            print(max)
        else:
            print(second)



def rank(arr):
    lastIndex = len(arr) - 1
    while lastIndex > 0:

        for i in range(lastIndex):
            if arr[i + 1] < arr[i]:
                tmp = arr[i + 1]
                arr[i + 1] = arr[i]
                arr[i] = tmp

        lastIndex = lastIndex - 1

    return arr



N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))

calculate(arr)



### FIXED CODE ###

def calculate(arr):

    largest,second = findLargetAndSecond(arr)

    for i in range(len(arr)):
        value = arr[i]
        if largest != value:
            print(largest)
        else:
            print(second)


def findLargetAndSecond(arr):
    largest = 0
    second = 0

    for i in range(0,len(arr)):
        if arr[i] > largest:
            second = largest
            largest = arr[i]
        else:
            if arr[i] >= second:
                second = arr[i]

    return largest,second



N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))

calculate(arr)
### BUGGY CODE ###


N,C = map(int,input().split())
h = list(map(int,input().split()))
#print(h)

dp = [0]*N
dp[0] = 0
for n in range(1,N):
	best = 99999999999999
	for k in range(1,N):
		if n-k<0: continue
		step = C+(h[n]-h[n-k])**2+dp[n-k]
		best = min(best,step)
	dp[n] = best

ans = dp[N-1]
print(ans)


### FIXED CODE ###


class ConvexHullTrick:
	length = 0

	def __init__(self,size):
		self.A = [0]*size
		self.B = [0]*size

	def check(self,a,b):
		lhs = (self.B[self.length-2]-self.B[self.length-1])*(a-self.A[self.length-1])
		rhs = (self.B[self.length-1]-b)*(self.A[self.length-1]-self.A[self.length-2])
		return lhs>=rhs

	# 直線の傾きaは単調現象であること
	# Add a line y=a*x+b
	def add(self,a,b):
		while 2<=self.length and self.check(a,b):
			self.length -= 1
		self.A[self.length] = a
		self.B[self.length] = b
		self.length += 1
		return
	# min_i {a[i]*x+b[i]}
	def query(self,x):
		l,r = -1, self.length-1
		while l+1<r:
			m = (l+r)//2
			if self.eval(m+1,x)<=self.eval(m,x):
				l = m
			else:
				r = m
		return self.eval(r,x)

	def eval(self,k,x):
		return self.A[k]*x + self.B[k]

N,C = map(int,input().split())
h = list(map(int,input().split()))
#print(h)

cht = ConvexHullTrick(N)

dp = [0]*N
dp[0] = 0
cht.add(-2*h[0],h[0]**2+dp[0])
for i in range(1,N):
	#best = 99999999999999
	# for j in range(i):
	# 	#cost = dp[j]+(h[i]-h[j])**2+C
	# 	cost = (-2*h[j])*h[i]+(h[j]**2+dp[j])
	# 	best = min(best,cost)
	best = cht.query(h[i])
	dp[i] = best+h[i]**2+C

	cht.add(-2*h[i],h[i]**2+dp[i])

ans = dp[N-1]
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans=0
K=int(input())
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans+=gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans=0
K=int(input())
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans+=gcd(a,b,c)
print(ans)
### BUGGY CODE ###

from collections import deque

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

vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)

S, T = map(int, input().split())
S, T = S - 1, T - 1

visited = [False] * N
visited[S] = True
queue1 = deque([(0, S)])

while queue1 :
    cost, i = queue1.popleft()
    queue2 = deque([(0, i)])
    
    while queue2 :
        step, q = queue2.popleft()
        if step == 2 : 
            for j in vec[q] :
                if j == T :
                    print(cost + 1)
                    exit()
                if not visited[j] :
                    visited[j] = True
                    queue1.append((cost + 1, j))
        else :
            for j in vec[q] :
                queue2.append((step + 1, j))

print(-1)
    

### FIXED CODE ###

from collections import deque

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

vec = [[] for _ in range(N)]
for _ in range(M) :
    u, v = map(int, input().split())
    vec[u-1].append(v-1)

S, T = map(int, input().split())
S, T = S - 1, T - 1

visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])

while queue :
    q, cost = queue.popleft()
    p = (cost + 1) % 3
    for i in vec[q] :
        if p == 0 and i == T :
            print((cost + 1) // 3)
            exit()
        if not visited[p][i] :
            visited[p][i] = True
            queue.append((i, cost + 1))

print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

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

root = {}
for i in range(n-1):
    a, b = map(int, input().split())
    root.setdefault(a, []).append(b)
    root.setdefault(b, []).append(a)
    
cnt = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

check = []
def rec(node, checked):
    for k in root[node]:
        if not k in checked:
            cnt[k] += cnt[node]
            if not node in checked:
                checked.append(node)
            rec(k, checked)

rec(1, check)
print(" ".join(map(str, cnt[1:])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)

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

root = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    root[a].append(b)
    root[b].append(a)
    
cnt = [0 for _ in range(n+1)]
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x

def rec(node, parent):
    for i in root[node]:
        if i == parent:
            continue
        cnt[i] += cnt[node]
        rec(i, node)

rec(1, 1)
print(" ".join(map(str, cnt[1:])))
### BUGGY CODE ###

from collections import deque
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
px=[list(map(int,input().split())) for _ in range(q)]

adlist=[]
finish=set()
def dfs():
    while deq:
        now=deq.pop()
       # print(now)
        finish.add(now)
        for i in range(len(adlist[now-1])):
            #print(adlist[now-1][i],now)
            if adlist[now-1][i] not in finish:
                point[adlist[now-1][i]-1]+=point[now-1]
                deq.append(adlist[now-1][i])
point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)
#print(deq)
dfs()
for i in range(n):
    print(point[i],end=" ")


### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
px=[list(map(int,input().split())) for _ in range(q)]

adlist=[]
finish=set()

point=[0]*n
for h in range(n):    
    adlist.append([])
for j in range(n-1):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
for i in range(q):
    point[px[i][0]-1]+=px[i][1]
#print(point)
deq=deque()
deq.append(1)


while deq:
    now=deq.pop()
       # print(now)
    finish.add(now)
    for i in range(len(adlist[now-1])):
        #print(adlist[now-1][i],now)
        if adlist[now-1][i] not in finish:
            point[adlist[now-1][i]-1]+=point[now-1]
            deq.append(adlist[now-1][i])

for i in range(n):
    print(point[i],end=" ")
### BUGGY CODE ###

N,M=map(int,input().split())
i=N
while(i*2 <=M):
    if(M%i==0):
        break
    i+=1
if(i*2>M):
    i=M
print(M//i)

### FIXED CODE ###

import sys
N,M=map(int,input().split())
i=N


gcd=1
while(1):
    if(M%i==0):
        print(M//i)
        sys.exit(0)
    if(i**2 >M):
        break
    i+=1

i=M//N
while(1):
    if(M%i==0):
        print(i)
        sys.exit(0)
    i-=1
### BUGGY CODE ###

import sys
import itertools
readline = sys.stdin.buffer.readline

X, Y, Z, K = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
C = list(map(int, readline().split()))
AB = [a+b for (a,b) in list(itertools.product(A,B))]
AB.sort(reverse=True)
ans = [ab + c for (ab,c) in list(itertools.product(AB[:K],C))]
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])

### FIXED CODE ###

import sys
import itertools
readline = sys.stdin.buffer.readline

X, Y, Z, K = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
C = list(map(int, readline().split()))
AB = [a+b for (a,b) in list(itertools.product(A,B))]
AB.sort(reverse=True)
ans = [ab + c for (ab,c) in list(itertools.product(AB[:K],C))]
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print(ans[i])

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v):
  pos=bisect.bisect_left(dp,arr[v])
  changes.append((pos,dp[pos]))
  dp[pos]=arr[v]
  ans[v]=bisect.bisect_left(dp,10**18)
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      dfs(u)
  pos,val=changes.pop()
  dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
changes=[]
dfs(1)
for i in range(1,n+1):
  print(ans[i])
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0

for x in range(k+1):
    for y in range(k+1):
        test = s-x-y
        if 0 <= test and test <= k:
            ans += 1

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

import numpy as np

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

d = 0
c = 1

m = 0
while m < n - 1:
    i = np.argmax(a[m:])
    if i == 0:
        m += 1
        continue
    #print(i,m, a[i], a[m:m+i])
    j = np.argmin(a[m:m+i])
    x = a[m+j]
    y = a[m+i]
    #print(x, y, i, j, y - x)
    if y - x == d:
        c += 1
    elif y - x > d:
        d = y - x
        c = 1
    m += i
    #print(m, a[m:])

print(c)


### FIXED CODE ###

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

m = a[0]
d = 0
c = 1

for i in range(1, n):
    if a[i] - m > d:
        d = a[i] - m
        c = 1
    elif a[i] - m == d:
        c += 1
    elif a[i] < m:
        m = a[i]

print(c)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(N-1+M)]
graph = [[] for _ in range(N)]
d_in = [0]*N
for a, b in AB:
	a, b = a-1, b-1
	graph[a].append(b)
	d_in[b] += 1

for i in range(N):
	if d_in[i] == 0:
		root = i
		break

ans = [None]*N
ans[root] = 0
q = deque([root])
while q:
	n = q.popleft()
	for node in graph[n]:
		ans[node] = n+1
		q.append(node)

print(*ans, sep="\n")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
AB = [LIST() for _ in range(N-1+M)]
graph = [[] for _ in range(N)]
d_in = [0]*N
for a, b in AB:
	a, b = a-1, b-1
	graph[a].append(b)
	d_in[b] += 1

for i in range(N):
	if d_in[i] == 0:
		root = i
		break

ans = [None]*N
ans[root] = 0
q = deque([root])
while q:
	n = q.popleft()
	for node in graph[n]:
		d_in[node] -= 1
		if d_in[node] == 0:
			ans[node] = n+1
			q.append(node)

print(*ans, sep="\n")
### BUGGY CODE ###

def main():
    X = int(input())

    a = -1
    b1 = -1
    b2 = 1
    while True:
    
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 = b1 + 1
            b2 = b2 - 1
            
        a += 1


if __name__ == "__main__":
    main()

          


### FIXED CODE ###

def main():
    X = int(input())

    a = -1
    
    while True:
        b1 = 0
        b2 = 0
        while b1 < a:
            
            if (X/(a-b1)).is_integer():
                if int(X/(a-b1)) == a**4 + b1*(a**3) + (a**2)*(b1**2) + a*(b1**3) + b1**4:
                    print("{} {}\n".format(a, b1))
                    return 0

            if (X/(a-b2)).is_integer():
                if int(X/(a-b2)) == a**4 + b2*(a**3) + (a**2)*(b2**2) + a*(b2**3) + b2**4:
                    print("{} {}\n".format(a, b2))
                    return 0

            b1 += 1
            b2 -= 1
            
        a += 1


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

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()

### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

import numpy
N,K=map(int,input().split())
A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        d[str(S2[j-K])] = d.get(str(S2[j-K]), 0) - 1
    d[str(S2[j-1])] = d.get(str(S2[j-1]), 0) + 1
    ans += d.get(str(S2[j]), 0)
print(ans)

### FIXED CODE ###

import numpy
N,K=map(int,input().split())

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

A=list(map(int,input().split()))
S=[0]+list(numpy.cumsum(A)) #累積和
S2=[(S[i]-i)%K for i in range(N+1)]

d = {}
ans = 0
for j in range(1,N+1):
    if j>K-1:
        if S2[j-K] in d:
            d[S2[j-K]] -= 1
        
    if S2[j-1] in d:
        d[S2[j-1]] += 1
    else:
        d[S2[j-1]] = 1
        
    if S2[j] in d:
        ans += d[S2[j]]
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(5)] + [0]
B = [n] + [0]*5
cnt = 0

while not B[5] == n:

    cnt+=1
    for i in range(5,0,-1):
        B[i] =B[i] - min(B[i],A[i]) + min(B[i-1],A[i-1])
    B[0] = B[0] - min(B[0],A[0])

print(cnt)

### FIXED CODE ###

import math
n = int(input())
A = [int(input()) for _ in range(5)]

print(4 + math.ceil(n/min(A)))
### BUGGY CODE ###

import collections

n = int(input())
s = input()
min_people = n - 1

def we_counter(pos):
  front = s[:pos]
  back = s[pos+1:]
  people = front.count('W') + back.count('E')
  return people


for i in range(n):
  people = we_counter(i)

  if people < min_people:
    min_people = people

print(min_people)


### FIXED CODE ###

n = int(input())
s = input()
point = [0]

def we_counter(pos):
  front = s[:pos]
  back = s[pos+1:]
  people = front.count('W') + back.count('E')
  return people


for i in range(n):
  if s[i] == 'W':
    point.append(point[i]-1)
  else:
    point.append(point[i]+1)

max_point = max(point)
pos = point.index(max_point)

print(we_counter(pos))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp = [[[-1] * 4 for _ in range(w)] for _ in range(h)]
    dp[0][0][0] = 0
    for i in range(h):
        for j in range(w):
            for c in range(4):
                pre = dp[i][j][c]
                if pre == -1: continue
                if i + 1 < h: dp[i + 1][j][0] = max(dp[i + 1][j][0], pre)
                if j + 1 < w: dp[i][j + 1][c] = max(dp[i][j + 1][c], pre)
                if c<3 and aa[i][j]:
                    if i + 1 < h: dp[i + 1][j][0] = max(dp[i + 1][j][0], pre + aa[i][j])
                    if j + 1 < w: dp[i][j + 1][c + 1] = max(dp[i][j + 1][c + 1], pre + aa[i][j])

    ans = 0
    for c in range(4):
        if c == 3: ans = max(ans, dp[h - 1][w - 1][c])
        else: ans = max(ans, dp[h - 1][w - 1][c] + aa[h - 1][w - 1])
    print(ans)

h,w,k=MI()
aa=[[0]*w for _ in range(h)]
for _ in range(k):
    i,j,v=MI()
    aa[i-1][j-1]=v
solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp0 = [0] * (w + 1)
    dp1 = [0] * (w + 1)
    dp2 = [0] * (w + 1)
    dp3 = [0] * (w + 1)
    for i in range(h):
        for j in range(w):
            v = vv[i * w + j]
            if v:
                dp3[j] = max(dp3[j], dp2[j] + v)
                dp2[j] = max(dp2[j], dp1[j] + v)
                dp1[j] = max(dp1[j], dp0[j] + v)
            dp3[j + 1] = max(dp3[j + 1], dp3[j])
            dp2[j + 1] = max(dp2[j + 1], dp2[j])
            dp1[j + 1] = max(dp1[j + 1], dp1[j])
            dp0[j] = max(dp1[j], dp2[j], dp3[j])
    print(dp0[-2])

h, w, k = MI()
vv = [0] * h * w
for _ in range(k):
    i, j, v = MI()
    i, j = i - 1, j - 1
    vv[i * w + j] = v
solve()
### BUGGY CODE ###

S=input()
ans=0
for i in range(len(S)+1):
  for j in range(i+3,len(S)+1):
    #print(S[i:j])
    if int(S[i:j])%2019==0:
      #print(int(S[i:j]))
      ans+=1
    
print(ans)

### FIXED CODE ###

'''冷めたコーヒー
入力文字列として、S = 31415926535を考えます。
このとき、例えば4番目から8番目までの部分文字列15926が
2019の倍数であるか判定したいというのが本問の主題です。
特定の部分文字列が2019の倍数であるかどうかは、
int(s[[i:j+1]) % 2019 == 0とすればよいのですが、
これを逐一やっていてはO(N^2)の計算量がかかってしまいます。
そこで、この部分文字列を次のようにとらえてみます。
15926=(15926535−535)/10^3
このように考えることの利点は、10^3 が 2019 と
互いに素（最大公約数が 1）であるため、
15926 が 2019 の倍数であるかどうかは、
上式右辺の分子に着目すればよいということです。
したがって、アルゴリズムを設計する際は、
与えられた文字列の右からk番目（0～n)から最右端までの
部分文字列を保持しておけばよいことになります。
分子が 2019 の倍数かどうかは、分子を A−B としたときに、
A mod2019 と B mod2019 の値がそれぞれ等しければ、
元の整数（上式左辺）は 2019 の倍数であると言えます。
'''
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019#2019で割った余りの個数をカウント
counts[0] = 1#その数が、ちょうど2019で割れた時のために必要

num, d = 0, 1

for char in s:
    num += int(char) * d#1桁目から数字を作る、整数型にする
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1#2019で割った余りの個数を足す1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2
    #余りが同じものを2つ選ぶ組み合わせの数が答

print(ans) # 答えの出力
### BUGGY CODE ###

s = input()
K = int(input())

strs = set()

for i in range(len(s)):
    for j in range(len(s) + 1):
        if i >= j:
            continue

        strs.add(s[i:j])

strs = sorted(strs)
print (strs[K - 1])

### FIXED CODE ###

s = input()
K = int(input())

strs = set()
for i in range(len(s)):
    for j in range(i + K + 1):
        if i >= j:
            continue

        strs.add(s[i:j])

strs = sorted(strs)
print (strs[K - 1])