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

N, M = (int(x) for x in input().split())

xyz = [list(map(int, input().split())) for _ in range(M)]

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
index = 0
for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    i = 0
    for a, b, _ in xyz:
        i+=1
        if i-1 <= index:
            continue
        a = a - 1
        b = b - 1
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True
    index+=1

magic_act_num += (N-judge)

print(magic_act_num)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.p[ry] = rx

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

    for i in range(M):
        x,y,_ = map(int, input().split())
        u.unite(x-1, y-1)

    rlist = set()
    for i in range(N):
        rlist.add(u.root(i))

    print(len(rlist))

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


N = map(int, input().split())
A = list(map(int, input().split()))
res = 0
for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] + A[j] == abs(i - j):
            res += 1
print(res)

### FIXED CODE ###

from collections import defaultdict
N = map(int, input().split())
A = list(map(int, input().split()))
res = 0
d = defaultdict(int)
for i, num in enumerate(A):
    res += d[i - num]
    d[i + num] += 1
print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
b = 1
c = 0
for i in range(N):
  b = b * A[i]
  if b > 10 ** 18:
    if A.count(0) == 0:
      c = 1
      break
if c == 0:
  print(b)
else:
  print(-1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
b = 1
c = 0
if A.count(0) != 0:
  print(0)
else:
  for i in range(N):
    b = b * A[i]
    if b > 10 ** 18:
      c = 1
      break
  if c == 0:
    print(b)
  else:
    print(-1)
### BUGGY CODE ###

N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(50*50)] for j in range(N+1) ]for k in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    for k in range(50*50):
      dp[i][j][k]=dp[i-1][j][k]
      if x[i-1]<= k and j>0: dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]
ans=0
for j in range(1,N+1):
  ans+=dp[N][j][j*A]
print(ans)

### FIXED CODE ###

N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0 for i in range(50*50+1)] for j in range(N+1) ]for k in range(N+1)]
dp[0][0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    for k in range(50*50+1):
      dp[i][j][k]=dp[i-1][j][k]
      if x[i-1]<= k and j>0: dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]
ans=0
for j in range(1,N+1):
  ans+=dp[N][j][j*A]
print(ans)
### BUGGY CODE ###

N=int(input())
A=[0]*5
for i in range(5):
    A[i]=int(input())
ans=0
B=[0]*6
B[0]=N
while B[5]<N:
    ans+=1
    for i in range(4,-1,-1):
        if B[i]>=A[i]:
            B[i+1]+=A[i]
            B[i]-=A[i]
        elif B[i]!=0:
            B[i+1]+=B[i]
            B[i]=0
print(ans)

### FIXED CODE ###

N = int(input())
A,B,C,D,E = map(int,[input() for i in range(5)])
ans = 0
def mymax(s):
    res = N//s
    if N%s==0:
        return res
    else:
        return res+1

k = max(mymax(A),mymax(B),mymax(C),mymax(D),mymax(E))
print(k+4)
### BUGGY CODE ###

import numpy as np

N,Ma,Mb = map(int,input().split())

dp = 99999999*np.ones((N+1,402,402),dtype=int)
dp[0][0][0] = 0
for n in range(N):
  a,b,c = map(int,input().split())
  for i in range(401):
    for j in range(401):
      if dp[n][i][j]!=99999999:
        dp[n+1][i  ][j  ] = min(dp[n+1][i  ][j  ],dp[n][i][j])
        dp[n+1][i+a][j+b] = min(dp[n+1][i+a][j+b],dp[n][i][j]+c)

ans = 99999999
i,j = Ma,Mb
while i<=401 and j<=401:
  ans = min(ans,dp[N][i][j])
  i += Ma
  j += Mb
print(ans if ans!=99999999 else -1)


### FIXED CODE ###

N,Ma,Mb = map(int,input().split())

sz = 401
table = [[99999999]*(sz+1) for _ in range(sz+1)]
table[0][0] = 0
for n in range(N):
  a,b,c = map(int,input().split())
  for i in range(sz,-1,-1):
    for j in range(sz,-1,-1):
      if table[i][j]!=99999999:
        table[i+a][j+b] = min(table[i+a][j+b],table[i][j]+c)
#print(table)

ans = 99999999
i,j = Ma,Mb
while i<=sz and j<=sz:
  ans = min(ans,table[i][j])
  i += Ma
  j += Mb
print(ans if ans!=99999999 else -1)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(i) for i in input().split()]
for i in range(m):
  A=max(a)
  ind=a.index(A)
  a[ind]=A//2
print(sum(a))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
for _ in range(m):
    heapq.heappush(a, heapq.heappop(a) * (-1) // 2 * (-1))
print(-sum(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
      	if next == prev:
        	continue
      	else:
          dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

for i in range(1,N+1):
    ans = a.index(i) + 1
    print(ans, end=" ")

### FIXED CODE ###

import numpy as np
def calc_1(x):
    return x+1

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

x = np.argsort(a)
hoge = list(map(calc_1,x))

ans = [str(a) for a in hoge]
ans = " ".join(ans)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
mod=10**9+7
power=1
for i in range(1,n+1):
    power=power*i%mod
print(power)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
c=1
for i in range(N):
  c=c*A[i]
if c>10**18:
  print(-1)
else:
  print(c)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
c=1
if 0 in A:
  print(0)
else: 
  for i in range(N):
    c=c*A[i]
    if c>10**18:
      c=-1
      break
    
  print(c)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        x = 4 * h * n - N * n - N * h
        if x != 0 and N * h * n % x == 0:
            w = N * h * n // x
            if w >= 1:
                print(h, n, w)
                exit()


### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        x = 4 * h * n - N * n - N * h
        if x != 0 and N * h * n % x == 0:
            w = N * h * n // x
            if w >= 1:
                print(h, n, w)
                exit()
### BUGGY CODE ###

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

B = []

for a in A:
  B.append(a)
  B.reverse()

for b in B:
  print(b, end=" ")

### FIXED CODE ###

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

B = []
T = []

if N % 2 == 0:
  for index, a in enumerate(A):
    if index % 2 == 1:
      T.append(a)
    else:
      B.append(a)
else:
  for index, a in enumerate(A):
    if index % 2 == 0:
      T.append(a)
    else:
      B.append(a)

T.reverse()
T.extend(B)


for b in T:
  print(b, end=" ")
### BUGGY CODE ###

n=int(input())
a=map(int,input().split())
x=10**18
ans=1
for i in a:
    ans=ans*i

if(ans>x):
  ans=-1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=10**18
ans=1
if 0 in a:
  ans=0
else:
  for i in a:
    ans=ans*i
    if(ans>x):
      ans=-1
      break
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 18] * (n+1)
dp[1] = 0
for i,v in enumerate(h,1):
  for j in range(i+1,min(n+1,i+k+1)):
    dp[j] = min(dp[j],dp[i]+abs(v-h[j-1]))
print(dp[n])


### FIXED CODE ###

n,k = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 18] * (n+1)
dp[1] = 0
for i,v in enumerate(h,1):
  for j in range(i+1,min(n+1,i+k+1)):
    dp[j] = min(dp[j],dp[i]+abs(v-h[j-1]))
print(dp[n])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = []
for i in range(1,len(A)+1,1):
    ans.append(A.index(i)+1)
print(*ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ans = [0]*N
for i,a in enumerate(A):
    ans[a-1] = i+1
print(*ans)
### BUGGY CODE ###

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check2(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)
### BUGGY CODE ###

import numpy as np
from numba import njit

H, W, M = map(int, input().split())

h = np.zeros(H + 1, np.int64)
w = np.zeros(W + 1, np.int64)
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x] += 1
    w[y] += 1
    boms.add((x, y))

h_max = h.max()
w_max = w.max()

h_idx = np.where(h == h_max)[0]
w_idx = np.where(w == w_max)[0]


@njit
def solve(h_max, w_max, boms):
    minus = []
    for x in h_idx:
        for y in w_idx:
            if (x, y) in boms:
                minus.append(-1)
            else:
                minus.append(0)
    return h_max + w_max + max(minus)


print(solve(h_max, w_max, boms))

### FIXED CODE ###

H, W, M = map(int, input().split())

h = [0] * H
w = [0] * W
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

h_max = max(h)
w_max = max(w)

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)
### BUGGY CODE ###

data = []

data = [int(input()) for _n in range(int(input()))]

for n in range(len(data)):
	print(max(data[0:n]+data[n+1:]))


### FIXED CODE ###

import copy

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
data2 = copy.copy(data)
data2.remove(maxInt)
max2Int = max(data2)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max2Int)
### BUGGY CODE ###

def f(s, n, a):
    if n == 0 and len(a) == 1:
        return 0
    c = 1
    for i in range(n):
        if not s[i] in a:
            c += f(s[i+1:], n-i-1, a+s[i])
    return c


N = int(input())
S = input()

print(f(S, N, ""))


### FIXED CODE ###

N = input()
S = input()
mod = 1000000007

d = {}
for c in S:
    if not c in d:
        d[c] = 1
    else:
        d[c] += 1

c = 1
for i in d.values():
    c *= (i+1)

print((c-1)%mod)
### BUGGY CODE ###

A=int(input())
list = []
for n in range(A):
	con = str(input())
	if con not in list:
		list.append(con)
	else: pass
print(str(len(list)))



### FIXED CODE ###

n = int(input())
s = set(input() for _ in range(n))
print(len(s))
### BUGGY CODE ###

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

from collections import defaultdict
k_y = defaultdict(int)
k_y[0] = 1000

#for hk,hy in k_y.items(): #所持株、金
#	print(hk,hy)

k_y_new = [ vvv for vvv in k_y.values()]
for i in range(n):
	for hk,hy in k_y.items(): #所持株、金
		kk = 0#想定所持株数
		while True:
			genkin = (hk - kk) * a[i] + hy
			
			if genkin < 0 :
				break
			else:
				if kk >= len(k_y_new):
					#print('add',genkin)
					k_y_new.append( genkin )
				else:
					#print('repl',k_y_new[kk], genkin)
					k_y_new[kk] = max(k_y_new[kk], genkin)
				kk = kk + 1
		#print( k_y_new )
	k_y = {x:y for x,y in enumerate(k_y_new)}
print( k_y_new[0] )


### FIXED CODE ###

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

k_y = [1000]
yen = 1000
resyen = 1000
kabu_max = 0
for i in range(n):
	#株を売り払うケース
	newyen = max( yen, kabu_max * a[i] + resyen)
	
	#株を最大買うケース
	kabu_max_new = max( kabu_max + resyen // a[i], yen // a[i] )
	if kabu_max_new == yen // a[i]:
		if kabu_max_new == kabu_max + resyen // a[i]:
			resyen = max( yen % a[i], resyen % a[i])
		else:
			resyen = yen % a[i]
	
	yen = newyen
	kabu_max = kabu_max_new
	#print(kabu_max,yen,resyen)
print( yen )
### BUGGY CODE ###

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

visited = [1]

for i in range(K):
    t = A[visited[-1] - 1]
    if t in visited:
        z = K - i - 1
        r = visited[visited.index(t):]
        l = len(r)
        print(r[z % l])
        exit()
    else:
        visited.append(t)

print(visited[-1])



### FIXED CODE ###

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

visited = {1: 0}
index = 0
last = 1

for i in range(K):
    t = A[last - 1]
    index += 1
    if t in visited:
        z = K - i - 1
        l = index - visited[t]
        print([k for k, v in visited.items() if v == visited[t] + (z % l)][0])
        exit()
    else:
        visited[t] = index
        last = t

print(last)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    W, V = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[float('inf')]*(10**5+10) for i in range(N+1)]
    # for i in range(150):
    #     dp[0][i] = 0
    dp[0][0] = 0

    for i in range(N):
        for v in range(10**5+10):
            if v - V[i] >= 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v - V[i]] + W[i])
            dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    ans = 0
    for v in range(10**5 + 10):
        if dp[N][v] <= M:
            ans = v
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    W, V = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[float('inf')]*(10**5+10) for i in range(N+1)]
    # for i in range(150):
    #     dp[0][i] = 0
    dp[0][0] = 0

    for i in range(N):
        for v in range(10**5+10):
            if v - V[i] >= 0:
                dp[i+1][v] = min(dp[i+1][v], dp[i][v - V[i]] + W[i])
            dp[i+1][v] = min(dp[i+1][v], dp[i][v])
    ans = 0
    for v in range(10**5 + 10):
        if dp[N][v] <= M:
            ans = v
    print(ans)

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

i = 1
N = int(input())
while True:
  if i % 2 == 0 and i % N == 0:
    print(i)
    break
  i = i + 1

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
  print(N)
else:
  print(N*2)
### BUGGY CODE ###

a,b,k = map(int, input().split())

for i in range(k):
  if(a>0):
    a-=1
    continue
  if(b>0):
    b-=1
    continue

print("{0} {1}".format(a,b))

### FIXED CODE ###

a,b,k = map(int, input().split())

if(a<k):
  k -= a
  a = 0
else:
  tmp = k
  k=0
  a -= tmp
  
if(b<k):
  b = 0
else:
  b -= k

print("{0} {1}".format(a,b))
### BUGGY CODE ###

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

mod = 1000000007
bit = pow(2, 59)
ans = 0
while bit != 0:
    cnt = 0
    for i in range(len(a)):
        if a[i] // bit == 1:
            cnt += 1
        a[i] %= bit
    ans += (cnt * (n-cnt) * bit)
    ans %= mod
    bit //= 2

print(ans)

### FIXED CODE ###

import numpy as np
mod = 1000000007

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

bit = 1
ans = 0
for i in range(60):
    a_and = a & 1
    cnt_one = np.count_nonzero(a_and)
    ans += (cnt_one * (n - cnt_one) * bit) % mod
    ans %= mod
    a >>= 1
    bit *= 2
    bit % mod

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

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for kk in range(4)] for jj in range(c+1)] for ii in range(r+1)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])#,dp[i][j-1][k])
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
                if k>0:
                    if dp[i][j][k]<dp[i][j-1][k-1]+g[i-1][j-1]:
                        dp[i][j][k]=dp[i][j-1][k-1]+g[i-1][j-1]
                if dp[i][j][1]<dp[i-1][j][k]+g[i-1][j-1]:
                    dp[i][j][1]=dp[i-1][j][k]+g[i-1][j-1]
    print(max(dp[r][c]))
if __name__=='__main__':
    main()



### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for jj in range(c+1)] for ii in range(r+1)] for kk in range(4)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])#,dp[i][j-1][k])
                dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[k][i][j]<dp[k-1][i][j-1]+g[i-1][j-1]:
                            dp[k][i][j]=dp[k-1][i][j-1]+g[i-1][j-1]
                    if dp[1][i][j]<dp[k][i-1][j]+g[i-1][j-1]:
                        dp[1][i][j]=dp[k][i-1][j]+g[i-1][j-1]
    print(max(dp[0][r][c],dp[1][r][c],dp[2][r][c],dp[3][r][c]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

def function(S):
    S_num = int(S)
    digit = len(S)
    multiple = 2019
    
    # make mod 2019 for each digit
    # 12114 -> 100
    # 2114 -> 2109
    # 114 -> 114
    digitAmari = []
    num = S_num
    while digit >= 0:
        digitAmari.append(num % multiple)
        num = num % pow(10, digit-1)
        digit -= 1
    
    # find same mod.
    # 余りが等しい場合、その区間は2019で割り切れるはず。
    kukans = []
    for i in range(0, len(digitAmari)):
        for j in range(i+1, len(digitAmari)):
            if digitAmari[i] == digitAmari[j]:
                kukans.append([i,j])
    return str(len(kukans))

if __name__ == '__main__':
    print(function(input()))


### FIXED CODE ###

def function(S):
    S = S[::-1]
    mods = [0]*2019 # mod 2019の余り0~2018の数
    mods[0] += 1 # 自身が割れる場合
    # MEMO : int(c) * 10^n % 2019 をまともに計算するとTLE
    # １つ前の桁のmodを利用する
    num = 0
    digit = 1
    for c in S:
        num = (int(c) * digit + num) % 2019
        digit = (digit * 10) % 2019
        mods[num] += 1
    
    result = 0
    for m in mods:
        result +=  m * (m-1) // 2

    return str(result)

if __name__ == '__main__':
    print(function(input()))