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

import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.child_num = 0
    
    def root_node(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, M = map(int, input().split())

    nodes = [Node() for i in range(N)]

    ab = [list(map(int, input().split())) for i in range(M)]
    
    inc = (N * (N-1)) // 2
    ans = [inc]
    for i in range(M-1, -1, -1):
        a, b = ab[i]
        a -= 1
        b -= 1
        root_a = nodes[a].root_node()
        root_b = nodes[b].root_node()
        if root_a == root_b:# もともと連結成分だった場合
            ans.append(inc)
        else:# 新たに連結成分になった場合
            # if root_b.child_num > root_a.child_num:
            #     tmp = root_a
            #     root_a = root_b
            #     root_b = tmp
            inc -= (root_a.child_num + 1) * (root_b.child_num + 1)
            ans.append(inc)
            root_b.is_root = False
            root_b.parent = root_a
            root_a.child_num += root_b.child_num + 1

    for i in range(M-1, -1, -1):
        print(ans[i])

if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.child_num = 0
    
    def root_node(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N, M = map(int, input().split())

    nodes = [Node() for i in range(N)]

    ab = [list(map(int, input().split())) for i in range(M)]
    
    inc = (N * (N-1)) // 2
    ans = [inc]
    for i in range(M-1, -1, -1):
        a, b = ab[i]
        a -= 1
        b -= 1
        root_a = nodes[a].root_node()
        root_b = nodes[b].root_node()
        if root_a == root_b:# もともと連結成分だった場合
            ans.append(inc)
        else:# 新たに連結成分になった場合
            if root_b.child_num > root_a.child_num:
                tmp = root_a
                root_a = root_b
                root_b = tmp
            inc -= (root_a.child_num + 1) * (root_b.child_num + 1)
            ans.append(inc)
            root_b.is_root = False
            root_b.parent = root_a
            root_a.child_num += root_b.child_num + 1

    for i in range(M-1, -1, -1):
        print(ans[i])

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

import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = ('0' + str(board0))[-9:].index('0')

appeared = {board0}
queue = list((0, move_from, p0, board0) for move_from in movables[p0])
heapq.heapify(queue)

while True:
    total_cost, move_from, move_to, board = heapq.heappop(queue)
    if board == destination:
        print(total_cost)
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared:
        continue
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, move_from2, move_from, new_board))

### FIXED CODE ###

import heapq
from itertools import chain
from operator import mul

exp10 = [10 ** a for a in range(8, -1, -1)]
movables = [{1, 3}, {0, 2, 4}, {1, 5}, {0, 4, 6}, {1, 3, 5, 7}, {2, 4, 8}, {3, 7}, {4, 6, 8}, {5, 7}]

destination = 123456780


def swap(board, move_from, move_to):
    return board + (exp10[move_to] - exp10[move_from]) * (board // exp10[move_from] % 10)


board0 = sum(map(mul, exp10, chain.from_iterable(map(int, input().split()) for _ in range(3))))
p0 = ('0' + str(board0))[-9:].index('0')

appeared = ({board0: 0}, {destination: 0})
queue = []
queue.extend((0, 0, move_from, p0, board0) for move_from in movables[p0])
queue.extend((0, 1, move_from, 8, destination) for move_from in movables[8])
heapq.heapify(queue)

while True:
    total_cost, direction, move_from, move_to, board = heapq.heappop(queue)
    if board in appeared[not direction]:
        print(total_cost + appeared[not direction][board])
        break
    new_board = swap(board, move_from, move_to)
    if new_board in appeared[direction]:
        continue
    appeared[direction][new_board] = total_cost + 1
    for move_from2 in movables[move_from]:
        if move_from2 != move_to:
            heapq.heappush(queue, (total_cost + 1, direction, move_from2, move_from, new_board))
### BUGGY CODE ###

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
com=1
for i in range(1, k+1):
  com=(((com*(n-i+1))%p)*modinv(i,p))%p
  if i==a:
    coma=com
  if i==b:
    comb=com
print((2**n-1-coma-comb)%p)


### FIXED CODE ###

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
k=max(a,b)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
com=[0]*(k+1)
com[0]=1
for i in range(1, k+1):
  com[i]=((com[i-1]*(n-i+1))*modinv(i,p))%p
print((pow(2,n,p)-1-com[a]-com[b])%p)
### BUGGY CODE ###

from math import factorial

MOD = 10 ** 9 + 7

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

F = {}
def fact_power(a, b):
    if (a, b) in F:
        return F[(a, b)]
    if b == 0:
        ans = 1
    elif b % 2 == 0:
        d = fact_power(a, b // 2)
        ans = (d * d) % MOD
    else:
        ans = (factorial(a) * fact_power(a, b - 1)) % MOD
    F[(a, b)] = ans
    return ans

P = {}
def perm(a, b):
    if b == 0 or a < b:
        return 0
    if (a, b) in P:
        return P[(a, b)]
    ans = fact_power(a - 1, 1) * fact_power(a - b, MOD - 2) * fact_power(b - 1, MOD - 2) % MOD
    P[(a, b)] = ans
    return ans

if N == K:
    print(1)
    for i in range(K - 1):
        print(0)
else:
    for i in range(1, K + 1):
        B = perm(K, i)
        R = perm(N - K, i - 1) + perm(N - K, i) * 2 + perm(N - K, i + 1)
        print(B * R % MOD)


### FIXED CODE ###

from math import factorial

MOD = 10 ** 9 + 7

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

f = {}
def fact(x):
    if x in f:
        return f[x]
    ans = factorial(x)
    f[x] = ans
    return ans

F = {}
def fact_power(a, b):
    if (a, b) in F:
        return F[(a, b)]
    if b == 0:
        ans = 1
    elif b % 2 == 0:
        d = fact_power(a, b // 2)
        ans = (d * d) % MOD
    else:
        ans = (fact(a) * fact_power(a, b - 1)) % MOD
    F[(a, b)] = ans
    return ans

P = {}
def perm(a, b):
    if b == 0 or a < b:
        return 0
    if (a, b) in P:
        return P[(a, b)]
    ans = fact_power(a - 1, 1) * fact_power(a - b, MOD - 2) * fact_power(b - 1, MOD - 2) % MOD
    P[(a, b)] = ans
    return ans

if N == K:
    print(1)
    for i in range(K - 1):
        print(0)
else:
    for i in range(1, K + 1):
        B = perm(K, i)
        R = perm(N - K, i - 1) + perm(N - K, i) * 2 + perm(N - K, i + 1)
        print(B * R % MOD)
### BUGGY CODE ###

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

S10 = [0 for i in range(10)]
S100 = [list(S10) for i in range(10)]
S1000 =[list([list(S10) for i in range(10)]) for i in range(10)]

for n in S:
    for i in range(10):
        for j in range(10):
            if list(S100)[i][j] == 1:
                S1000[i][j][int(n)] = 1
        if list(S10)[i] == 1:
            S100[i][int(n)] = 1
    S10[int(n)] = 1
    


ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if S1000[i][j][k] == 1:
                ans += 1

print(ans)


### FIXED CODE ###

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

S10 = [0 for i in range(10)]
S100 = [list(S10) for i in range(10)]
S1000 =[list([list(S10) for i in range(10)]) for i in range(10)]

for n in S:
    for i in range(10):
        for j in range(10):
            if list(S100)[i][j] == 1:
                S1000[i][j][int(n)] = 1
        if list(S10)[i] == 1:
            S100[i][int(n)] = 1
    S10[int(n)] = 1
    


ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if S1000[i][j][k] == 1:
                ans += 1

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


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

ans = 0
r = range(N)
kumis = []
for i in r:
    for j in r:
        if j < i: continue
        for k in r:
            if k < j: continue
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                kumis.append(tuple([i,j,k]))

for kumi in kumis:
    i,j,k = kumi
    if j-i != k-j:
        ans+=1

print(ans)

### FIXED CODE ###


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

r = S.count("R")
g = S.count("G")
b = S.count("B")

all_case = r*g*b

excluded_case = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]: continue
        k = j*2-i
        if k>= N or S[k] == S[i] or S[k] == S[j]: continue
        excluded_case += 1

print(all_case-excluded_case)
### BUGGY CODE ###

#d
import copy
n = int(input())
n_list = []
ans = 0
for i in range(1,n):
    ans += i
print(ans)

### FIXED CODE ###

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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            candidates.append(b)
        else:
            s = j
            break
    if len(candidates) > 0:
        max_v = max(candidates)
        candidates.pop(candidates.index(max_v))
        ans += max_v

print(ans)



### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            heapq.heappush(candidates, -b)
        else:
            s = j
            break
    else:
        s = j + 1
    if len(candidates) > 0:
        # print(candidates)
        ans += -1 * heapq.heappop(candidates)

print(ans)
"""
4 3 2

3 2 3 1
2 3 1


"""
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: y//gcd(x,y)*x, a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

### FIXED CODE ###

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)
### BUGGY CODE ###

n,a,b=map(int,input().split())
I=10**9+7
l=[1,1]
p=2
for i in range(1,n):
  p=p*2%I
  m=[1]
  for j in range(i):
    m.append((l[j]+l[j+1])%I)
  l=m+[1]
print((p-l[a]-l[b]-1)%I)

### FIXED CODE ###

n,a,b=map(int,input().split())
M=10**9+7
def c(k):
  s=t=1
  for i in range(k): s=s*(n-i)%M; t=t*(i+1)%M
  return s*pow(t,M-2,M)%M
print((pow(2,n,M)-c(a)-c(b)-1)%M)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    N = int(readline())
    to = [[] for _ in range(N)]
    wight = [[-1 for _ in range(N)] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, readline().split())
        u-=1
        v-=1
        to[u].append(v)
        to[v].append(u)
        wight[u][v] = w%2
        wight[v][u] = w%2

    dq = deque()
    dq.append(0)
    dist = [-1 for _ in range(N)]
    dist[0] = 0
    while len(dq)>0:
        v = dq.popleft()
        for nx in to[v]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[v]^wight[v][nx]
            dq.append(nx)

    for i in dist:
        print(i)
if __name__ == '__main__':
    main()


### FIXED CODE ###

#python3
from collections import deque
def main():
    n = int(input()) 
    #隣接リスト表現でグラフを管理する
    #v-uのcostはto[v]においてuが格納されている位置と同じcost[v]リスト位置に保存するような対応関係をとる
    to = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for _ in range(n-1):
        v, u, w  = map(int, input().split())
        v -= 1
        u -= 1
        to[v].append(u)
        cost[v].append(w)
        to[u].append(v)
        cost[u].append(w)

    
    #根からの距離を偶奇をBFSで求める    
    dist = [-1 for _ in range(n)]
    dist[0] = 0
    q = deque()
    q.append(0)
    while len(q) != 0:
        #訪問予定の頂点を取り出す
        val = q.popleft()
        #頂点vに連結している頂点を探索すして訪問予定に追加する
        for i in range(len(to[val])):
            wal = to[val][i]
            cos = cost[val][i]
            if dist[wal] != -1:
                continue
            dist[wal] = (dist[val] + cos)%2 
            q.append(wal)
    
    for i in range(n):
        print(dist[i])
main()
### BUGGY CODE ###

a, b = map(int, input().split())
cd = set()
ans = 0

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        cd.add(i)


for s in cd:
    if s == 1:
        ans += 1
    else:
        for t in range(2, s // 2 + 1):
            if s % t == 0:
                break
        else:
            ans += 1

print(ans)


### FIXED CODE ###

import math
from fractions import gcd

a, b = map(int, input().split())
cd = set()
ans = set()

'''
g = gcd(a, b)

for i in range(1, g+1):
    if a % i == 0 and b % i == 0:
        cd.add(i)
        '''

i =  1
a_set = set()

for i in range(1, int(math.sqrt(a)) + 1):
    if a % i == 0:
        a_set.add(i)
        a_set.add(a // i)
    i += 1

i = 1
b_set = set()

for i in range(1, int(math.sqrt(b)) + 1):
    if b % i == 0:
        b_set.add(i)
        b_set.add(b // i)
    i += 1

cd = set(a_set) & set(b_set)

for s in sorted(list(cd)):
    if s == 1:
        ans.add(s)
    else:
        for t in sorted(list(ans)):
            if t == 1:
                continue
            elif s % t == 0:
                break
        else:
            ans.add(s)

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

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

b = []
for i in range(n):
    if i % 2 == 1:
        b.append(a[i])
    else:
        b.insert(0,a[i])


if n % 2 == 1:
    for i in b:
        print(i, end=" ")
else:
    for i in reversed(b):
        print(i, end=" ")


### FIXED CODE ###

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

b = [0] * n


if n % 2 == 1:
    for i in reversed(range(n)):
        if i % 2 == 1:
            b[n // 2 + int(i/2 + 0.9)] = a[i]
        else:
            b[n // 2 - int(i/2 + 0.9)] = a[i]
else:
    for i in reversed(range(n)):
        if i % 2 == 1:
            b[n // 2 - 1 + int(i/2 + 0.9)] = a[i]
        else:
            b[n // 2 - 1 - int(i/2 + 0.9)] = a[i]


if n % 2 == 1:
    for i in b:
        print(i, end=" ")
else:
    for i in reversed(b):
        print(i, end=" ")
### BUGGY CODE ###

N = int(input())
result = True

for _ in range(N):
    a = list(map(int, input().split()))
    
    if(abs(a[1]) + abs(a[2]) not in list(range(a[0] + 1))[a[0] % 2 == 1: : 2]):
        result = False
    
print(('No', 'Yes')[result])

### FIXED CODE ###

N = int(input())
txy = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(N)]
result = True

for i in range(N):
    dt = txy[i + 1][0] - txy[i][0]
    dist = abs(txy[i + 1][1] - txy[i][1]) + abs(txy[i + 1][2] - txy[i][2])
    
    if(dist > dt): result = False
    if(dist % 2 != dt % 2): result = False

print(("No", "Yes")[result])
### BUGGY CODE ###


n=input()
ans=0
i=0
b=list(map(int,input().split()))
print(b)
b=list(map(lambda x:x/2,b))
print(b)
while 1.0 or 0 not in b:
    b=list(map(lambda x:x/2,b))
    ans+=1
for x in b:
    if x%2==1:
        ans=0
print(ans)


### FIXED CODE ###


n=input()
ans=0
i=0
b=list(map(int,input().split()))

end=True
while end:
    for x in b:
        if x%2!=0:
            print(ans)
            end=False
            break
    b=list(map(lambda x:x/2,b))
    ans+=1
### BUGGY CODE ###

from collections import deque
n = int(input())
A = deque(sorted(list(map(int, input().split())), reverse = True))

ans = 0
while len(A) > 0:    
    f = 0
    ans += 1
    s = A.pop()
    N = deque([])
    if len(A) == 0:
        break
    else:
        for i in range(len(A)):
            t = A.popleft()
            if t == s:
                f = 1
            elif t % s == 0:
                f = 0
            else:
                N.append(t)

        A = N
        #print(A)

        if f == 1:
            ans -= 1
        else:
            pass

print(ans)

### FIXED CODE ###

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

Cnt = [0 for i in range(10**6 + 8)]
for i in A:
    if Cnt[i] != 0:
        Cnt[i] = 2
        continue
    else:
        pass
    for j in range(i, 10**6 + 8, i):
        Cnt[j] += 1

ans = 0
for i in A:
    if Cnt[i] == 1:
        ans += 1
    else:
        pass

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

import fractions
from functools import reduce
import copy

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

def gcd_list(*numbers):
    return reduce(fractions.gcd, numbers)

ans = 0
for i in range(N):
    a = copy.copy(A)
    a.pop(i)
    kouyaku = gcd_list(*a)
    ans = max(ans, kouyaku)

print(ans)

### FIXED CODE ###

import fractions

N = int(input())
A = list(map(int,input().split()))
l = [0] * (N+1)
r = [0] * (N+1)

for i in range(1, N+1):
    l[i] = fractions.gcd(l[i-1], A[i-1])
for i in range(1, N+1):
    r[N-i] = fractions.gcd(r[N-i+1], A[N-i])

ans = 0
for i in range(N):
    kouyaku = fractions.gcd(l[i], r[i+1])
    ans = max(ans, kouyaku)

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

p = lambda  x: x #print(x)
 
PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""
 
# def fnc(a, ans):
# 	for i in range(N-1):
# 		if ans != "": break
# 		x = a[N-1-i]
# 		for j in range(N-1):
# 			y = a[j]
# 			if x-y == K:
# 				ans = PO
# 				break
# 			elif x-y < 0:
# 				break
# 			else:
# 				if (x-y) not in a:
# 					a.insert(0,x-y)
# 					print(a)
# 	else:
# 		ans = IM
	
 
N, K = map(int, input().split())		# 5 7
a = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
a.sort()
p(a)
 
if max(a)<K:
	ans = IM
 
if K in a:
	ans = PO
 
if ans == "":
	for i in range(N-2):
		x = a[i]
		p(x)
		for j in range(i+1, N-1):
			y = a[j]
			p(y)
			b = y%x
			p(b)
			if b!=0 and K%b == 0:
				ans = PO
				p("A")
				break
 
		if ans != "": break
	else:
		ans = IM
		p("B")
 
 
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""


N, K = map(int, input().split())		# 5 7
a = sorted(list(map(int, input().split())))	# 1 2 3 4 5 ...

if max(a)<K:
	print(IM)
	sys.exit()

if K in a:
	print(PO)
	sys.exit()

g=a[0]
for i in range(1,N):
	g = gcd(g,a[i])

if K%g==0:
	ans=PO
else:
	ans=IM


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

S = input()

r_list = [0 for _ in range(2019)]
r_list[0 % 2019] += 1
for i in range(1,len(S)+1):
    r_list[int(S[len(S)-i:]) % 2019] += 1

ans = r_list[0] - 1
for i in range(1,2019):
    if r_list[i] >= 2:
        ans += r_list[i]*(r_list[i]-1)//2

print(ans)


### FIXED CODE ###

S = input()
s_rev = S[::-1]

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

ans = 0
for i in range(2019):
        ans += r_list[i]*(r_list[i]-1)//2

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

import sys
*data, = map(int, sys.stdin.read().split()[::-1])
def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(R + 1):
    dp.append([[0] * (4) for _ in range(C + 1)])


mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        for level in range(4):
            dp[row][col][0] = max(dp[row][col][0], dp[row - 1][col][level])
            dp[row][col][1] = max(dp[row][col][1], dp[row - 1][col][level] + grid[row - 1][col - 1])
        for level in range(1, 4):
            dp[row][col][level] = max(
                dp[row][col][level],
                dp[row][col - 1][level - 1] + grid[row - 1][col - 1],
                dp[row][col - 1][level]
            )
            mx = max(mx, dp[row][col][level])

print(mx)


### FIXED CODE ###

import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


dp = []
for _ in range(4):
    dp.append([[0] * (C + 1) for _ in range(R + 1)])

# print(time.time() - s1)
mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        dp[1][row][col] = max(dp[1][row][col], dp[3][row - 1][col] + grid[row - 1][col - 1])
        dp[0][row][col] = max(dp[0][row][col], dp[3][row - 1][col])
        level = 1
        v = grid[row - 1][col - 1]
        while level < 4:
            dp[level][row][col] = max(
                dp[level - 1][row][col],
                dp[level][row][col],
                dp[level][row][col - 1],
                dp[level - 1][row][col - 1] + v,
            )
            mx = max(mx, dp[level][row][col])
            level += 1

# print(time.time() - s1)
print(mx)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    ansls = [0]*(n+1)

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = set([int(input()) for _ in range(m)])

    ansls = [0]*(n+1)
    big = 10**9 + 7

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%big
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###


s = input()
K = int(input())
len_s = len(s)

result = []

for i in range(len_s):

  count = 0
  for j in range(i+1, len_s+1):
    if count > 5:
      break
    x = s[i:j]
    if x not in result:
      result.append(x)
    count += 1

print(sorted(result)[K-1])

### FIXED CODE ###

# 問題文をよく読んで、制約をヒントに答えを導かないといけない問題

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

result = []

len_s = len(s)
for i in range(len_s):
  for j in range(min(len_s, 5)):
    if s[i:i+j+1]:
      result.append(s[i:i+j+1])

ans = []
for res in sorted(result):
  if not res in ans:
    ans.append(res)
    if len(ans) == K:
      print(ans[K-1])
      exit()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0] + [sum(A[:i+1]) % M for i in range(N)]
B.sort()
ans = 0
k = 1
C = []
for i in range(N):
    if B[i] == B[i + 1]:
        k += 1
    else:
        C.append(k)
        k = 1
C.append(k)
for k in C:
    if k > 1:
        ans += k * (k - 1) // 2
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]
b = 0
for i in range(N):
    b += A[i]
    B.append(b % M)
B.sort()
ans = 0
k = 1
C = []
for i in range(N):
    if B[i] == B[i + 1]:
        k += 1
    else:
        C.append(k)
        k = 1
C.append(k)
for k in C:
    if k > 1:
        ans += k * (k - 1) // 2
print(ans)