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

def comb(n):
    return n * (n - 1) // 2

class UnionFind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

    def cost(self):
        result = 0
        for i in range(len(self.table)):
            if self.table[i] < 0:
                result += comb(-self.table[i])
        return result


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

A = [0] * M
B = [0] * M
for i in range(M):
    A[M - i - 1], B[M - i - 1] = [int(i) - 1 for i in input().split()]

uf = UnionFind(N)

result = comb(N)
lst = [result]
for i in range(M - 1):
    uf.union(A[i], B[i])
    lst.append(result - uf.cost())

lst.reverse()

for li in lst:
    print(li)


### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

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

A = [0] * M
B = [0] * M
for i in range(M):
    A[M - i - 1], B[M - i - 1] = [int(i) - 1 for i in input().split()]

uf = UnionFind(N)

result = N * (N - 1) // 2
lst = [result]
for i in range(M - 1):
    if not uf.same(A[i], B[i]):
        result -= uf.size(A[i]) * uf.size(B[i])
    lst.append(result)
    uf.union(A[i], B[i])

for i in range(M - 1, -1, -1):
    print(lst[i])
### BUGGY CODE ###

import sys
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
 
H,A=map(int,input().split())

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

li=sorted(l,reverse=True)

for _ in range(min(H,A)):
	li.pop(0)
	
print(sum(li))

### FIXED CODE ###

import sys
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
 
H,A=map(int,input().split())

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

li=sorted(l)

for _ in range(min(H,A)):
	li.pop()
	
print(sum(li))
### BUGGY CODE ###

n=int(input())
a=(input().split())
for i in range(n):
    x=0
    for j in range(n):
        for k in range(n):
            if j==i:
                pass
            elif k==i or j==k:
                pass       
            elif j>k and a[j]==a[k] and j!=i and k!=i:
                x=x+1
    print(x)


### FIXED CODE ###

def main():
    from collections import Counter
    n=int(input())
    a=list(map(int,input().split()))

    ctr = Counter(a)
    frm_n = sum(x * (x - 1) // 2 for x in ctr.values())

    ans = []
    for x in a:
        ans.append(frm_n - ctr[x] + 1)

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


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok
### BUGGY CODE ###

N = int(input())

C=[]
S=[]
F=[]

for i in range(N-1):
  a,b,c = map(int,input().split())
  C.append(a)
  S.append(b)
  F.append(c)

for i in range(N):
  if i == N-1:
    print(0)
  else:
    T = S[i]+C[i]
    for k in range(i+1,N-1):
      a = 0
      while T > S[k]+a*F[k]:
        a+=1
      T = S[k]+a*F[k]+C[k]
    print(int(T))


### FIXED CODE ###

N = int(input())
C=[]
S=[]
F=[]
for i in range(N-1):
  a,b,c = map(int,input().split())
  C.append(a)
  S.append(b)
  F.append(c)

for i in range(N-1):
  T = 0
  for j in range(i,N-1):
    if T < S[j]:
      T = S[j]
    elif T%F[j]==0:
      T = T
    else:
      T = T+F[j] - T%F[j]
    T = T + C[j]
  print(T)
print(0)
### BUGGY CODE ###

n, m, p = [ int(v) for v in input().split() ]
node_list = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,p-c))
distance_list = [ 10**15 for i in range(n) ]
parent_list = [ -1 for i in range(n) ]

distance_list[0] = 0
parent_list[0] = -1



for i in range(n-1):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_1 = [ i for i in distance_list]

for i in range(n):
    new_distanece_list = distance_list
    for j in node_list:
        a, b, c = j
        if distance_list[a] != 10**15:
            if new_distanece_list[b] > distance_list[a] + c:
                new_distanece_list[b] = distance_list[a] + c
                parent_list[b] = a
                change_log = 1
    distance_list = new_distanece_list
distance_list_2 = distance_list



if distance_list_1[-1] == distance_list_2[-1]:
    print(-min(0,distance_list_1[-1]))
else:
    print(-1)

### FIXED CODE ###

n, m, p = [ int(v) for v in input().split() ]
node_list = []
node_list_2 = []
for i in range(m):
    a, b, c = [ int(v) for v in input().split() ]
    node_list.append((a-1,b-1,p-c))
    node_list_2.append((b-1,a-1,p-c))


def b_f(node_list,n,t):
    distance_list = [ 10**15 for i in range(n) ]
    distance_list[t] = 0

    for i in range(n):
        new_distanece_list = distance_list
        for j in node_list:
            a, b, c = j
            if distance_list[a] != 10**15:
                if new_distanece_list[b] > distance_list[a] + c:
                    new_distanece_list[b] = distance_list[a] + c
        distance_list = new_distanece_list

        if i == n-2:
            distance_list_n_minus_1 = [i for i in distance_list]
        elif i == n-1:
            distance_list_n = [i for i in distance_list]

    if distance_list_n_minus_1 == distance_list_n:
        negative_cycle = 0
    else:
        negative_cycle = 1

    return distance_list_n_minus_1, negative_cycle


point_list_s = b_f(node_list,n,0)[0]
point_list_g = b_f(node_list_2,n,n-1)[0]
point_list = [ True for i in range(n) ]

for i in range(n):
    if point_list_s[i] == 10**15 or point_list_g[i] == 10**15:
        point_list[i] = False

node_list_3 = [ i for i in node_list if point_list[i[0]] == True and point_list[i[1]] == True ]
ans = b_f(node_list_3,n,0)

if ans[1] == 0:
    print(-min(0,ans[0][-1]))
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = []

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != []:
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.pop(0)
        Tree[child] = []
print(answer)

### FIXED CODE ###

import numpy as np
from collections import deque

N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = deque()

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != deque():
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.popleft()
print(answer)
### BUGGY CODE ###

import heapq

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

heapq.heapify(a) # in-place

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        temp = heapq.heappop(a)
        if c > temp:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, temp)
            break

print(sum(a))

### FIXED CODE ###

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

bc = []

for _ in range(m):
    b, c = map(int, input().split())
    bc.append((b, c))

bc = sorted(bc, key=lambda x: x[1], reverse=True)

cnt = 0

for b, c in bc:
    cnt += b
    a += [c] * b
    if cnt >= n:
        break

print(sum(sorted(a,reverse=True)[:n]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
import numpy as np
MAX = max(A)
BIG = 10**9+7
L = len(bin(MAX)[2:])
ans = 0
for j in range(L):
    zero = 0
    one = 0
    for i in range(N):
        if (A[i] >> j) & 1:
            one+=1
        else:
            zero+=1
    ans += zero*one*2**j
    ans = ans%BIG
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
BIG = 10**9+7
L = len(bin(MAX)[2:])
ans = 0
for j in range(L):
    zero = 0
    one = 0
    for i in range(N):
        if (A[i] >> j) & 1:
            one+=1
        else:
            zero+=1
    ans += ((zero*one)%BIG)*pow(2,j,BIG)
    ans = ans%BIG
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

    spl_l=[]
    for aaa in range(h):
        spl_l.append(sum(tmp[:aaa]))
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = spl_l[j]
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

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

N=int(input())

A=1
for a in [int(x) for x in input().split()]:
  A*=a
print(A if A<=10**18 else -1)


### FIXED CODE ###

N=int(input())

A=sorted([int(x) for x in input().split()],reverse=True)
if A[-1]==0:
  print(0)
else:
  m=1
  for a in A:
    m*=a
    if m>10**18:
      break
  print(m if m<=10**18 else -1)
### BUGGY CODE ###

MOD = 10**9+7
MAXN = 5*(10**5)+5
fact = [1]
ifact = [1]
for i in range(MAXN):
    fact.append(fact[-1] * (i+1) % MOD)
    ifact.append(pow(fact[-1], MOD-2, MOD))
def nCr(n, r):
    return fact[n] * ifact[r] * ifact[n-r] % MOD

def nPr(n, r):
    return fact[n] * ifact[n-r] % MOD

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    # tmp = pow(nPr(m-k, n-k), 2, MOD) * nPr(m, k) * nCr(n,k) % MOD
    # tmp = nPr(m-k, n-k) * nPr(m, n) * nCr(n,k) % MOD
    tmp = nPr(m-k, n-k) * nCr(n,k) % MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans = (ans * nPr(m, n) + MOD) % MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7
MAXN = 5*(10**5)+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def nPr(n, r, mod=MOD):
    return f[n] * pow(f[n-r], mod-2, mod) % mod

n, m = map(int, input().split())
ans = 0
for k in range(n+1):
    tmp = nPr(m-k, n-k)
    tmp *= tmp
    tmp %= MOD
    tmp *= nPr(m, k)
    tmp %= MOD
    tmp *= nCr(n,k)
    tmp %= MOD
    if k%2:
        ans -= tmp
    else:
        ans += tmp
ans += MOD
ans %= MOD
print(ans)
### BUGGY CODE ###

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

ans = 0
for l in range(n):
    temp_xor = a_list[l]
    temp_sum = a_list[l]
    ans += 1
    for r in range(l + 1, n):
        temp_xor ^= a_list[r]
        temp_sum += a_list[r]
        if temp_xor == temp_sum:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

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

ans = 0
temp_xor = a_list[0]
temp_sum = a_list[0]
r = 0
for l in range(n):
    while r < n:
        if temp_xor != temp_sum:
            break
        r += 1
        if r < n:
            temp_xor ^= a_list[r]
            temp_sum += a_list[r]
    ans += r - l
    temp_xor ^= a_list[l]
    temp_sum -= a_list[l]
print(ans)
### BUGGY CODE ###

import sys
n=int(input())
lst=[[] for i in range(n**2)]
li=[[] for i in range(n**2)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n-2):
        i1=i
        i2=i
        b=a[j]-1
        c=a[j+1]-1
        if i1>b:
            i1,b=b,i1
        if i2>c:
            i2,c=c,i2
        lst[n*i1+b].append(n*i2+c)
        li[n*i2+c].append(n*i1+b)
que=[1]
for _ in range(n*(n-1)//2+1):
    h=[]
    for u in que:
        for v in lst[u]:
            h.append(v)
    if not h:
        break
    que=h
else:
    print(-1)
    sys.exit()
count=0
while que:
    h=[]
    for u in que:
        for v in li[u]:
            h.append(v)
    que=h
    count+=1
    if count==n*(n-1)//2+1:
        print(-1)
        sys.exit()
print(count)

### FIXED CODE ###

n=int(input())
lst_to=[[] for i in range(n**2)]
lst_from=[[] for i in range(n**2)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n-2):
        i1=i
        i2=i
        b=a[j]-1
        c=a[j+1]-1
        if i1>b:
            i1,b=b,i1
        if i2>c:
            i2,c=c,i2
        lst_to[n*i1+b].append(n*i2+c)
        lst_from[n*i2+c].append(n*i1+b)

que=[]
for i in range(n):
    for j in range(i+1,n):
        if not lst_from[n*i+j]:
            que.append(n*i+j)

count=0
while que:
    count+=1
    h=[]
    for u in que:
        for v in lst_to[u]:
            lst_from[v].remove(u)
            if not lst_from[v]:
                h.append(v)
    que=h

for i in range(n):
    for j in range(i+1,n):
        if lst_from[n*i+j]:
            print(-1)
            break
    else:
        continue
    break
else:
    print(count)
### BUGGY CODE ###

n = int(input())
s = list(input())

a = 0

for i in range(n):
  if s[i]=='R':
    for j in range(n):
      if s[j]=='G':
        for k in range(n):
          if s[k]=='B':
            if i<j<k:
              if (j-i)!=(k-j):
                a = a + 1
            elif j<k<i:
              if (k-j)!=(i-k):
                a = a + 1
            elif k<i<j:
              if abs(j-i)!=abs(k-i):
                a = a + 1
            elif j<i<k:
              if abs(j-i)!=abs(k-i):
                a = a + 1
            elif i<k<j:
              if abs(k-i)!=abs(k-j):
                a = a + 1
            elif k<j<i:
              if abs(j-i)!=abs(k-j):
                a = a + 1
          
print(a)

### FIXED CODE ###

n = int(input())
s = input()
 
count = {"R":0,"G":0,"B":0}
for c in s:
    count[c] += 1
 
r,g,b = count.values()
ans = r*g*b
for i in range(1,(n-1)//2+1): #1から
    for rgb in zip(s,s[i:],s[i*2:]):  #rgbに連続した三つのリストの要素を入れ込む
        if len(set(rgb)) == 3:  #リストrgbをセットにまとめ、長さが
            ans -=1
print(ans)
### BUGGY CODE ###

import numpy as np

N, X = map(int, input().split())
S = input().split()

MOD = 1000000007
numbers = np.array(S).astype(np.int64)
numbers.sort()


dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
i = 0
for n  in numbers:
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n
    i += 1

print(int(dp_n[X]) % MOD)


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

S = input()
len_s = len(S)
while(True):
    S = S.replace("01","")
    S = S.replace("10", "")
    if not "01" in S:
        if not "10" in S:
            break
print(len_s - len(S))

### FIXED CODE ###

S = input()
if len(S) == 1:
    print(0)
else:
    print(min(S.count('0'), S.count('1')) * 2)
### BUGGY CODE ###

s = str(input())

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if i+2 <= len(s)-1:
        if s[i] == s[i+1]:
            s[i+1] = s[i+1] + s.pop(i+2)
    
if s[-1] == s[-2]:
    print(len(s) - 1)
else:
    print(len(s))

### FIXED CODE ###

s = str(input())

j = 0
count = len(s)

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if j+1 <= len(s)-1:
        if s[j] == s[j+1]:
            j = j + 3
            count -= 1
        else:
            j = j + 1
            continue

print(count)
### BUGGY CODE ###

import sys

N, M = map(int, input().split())
way_list = list()
first_list = list()
for i in range(M):
    a, b = map(int, input().split())
    if b == N:
        way_list.append(a)
    if a == 1:
        first_list.append(b)

for first in first_list:
    if first in way_list:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

from math import factorial
n = int(input())
list1 = [list(list(input())) for i in range(n)]
list2 = []
cout = 0

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))

for i in range(n):
    list1[i].sort()
    if list1[i] in list2:
        list2[list2.index(list1[i])+1].append(1)
    else:
        list2.append(list(list1[i]))
        list2.append([1])

for i in range(1,len(list2),2):
    if len(list2[i]) != 1:
        cout += combinations_count(sum(list2[i]),2)
print(cout)


### FIXED CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
n = int(input())
list1 = [''.join(sorted(input())) for i in range(n)]
dict1 = dict()
cout = 0
@lru_cache(maxsize = None)
def func(s):
	if s == 2:
		return 1 #2個の場合は1パターン
	return s-1 + func(s-1)

for i in range(n):
	if list1[i] in dict1:
		dict1[list1[i]] += 1
	else:
		dict1[list1[i]] = 1

for i in dict1:
	if dict1[i] != 1:
		cout += func(dict1[i])

print(cout)
### BUGGY CODE ###

import sys

def input():
    return sys.stdin.readline()[:-1]


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

for i in range(k):
    b = [0] * n
    for j in range(n):
        l = max(0, j-a_li[j])
        r = min(n-1, j+a_li[j])
        b[l] += 1
        if (r+1<n):
            b[r+1] -= 1
    for j in range(n-1):
        b[j+1] += b[j]
    a_li = b
print(*a_li)

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline()[:-1]


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

if k>=42:
    print(*[n]*n)
    exit()

for i in range(k):
    b = [0] * n
    for j in range(n):
        l = max(0, j-a_li[j])
        r = min(n-1, j+a_li[j])
        b[l] += 1
        if (r+1<n):
            b[r+1] -= 1
    for j in range(n-1):
        b[j+1] += b[j]
    a_li = b
print(*a_li)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp = np.zeros((3005, 3005, 4), dtype=np.int64)

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp[i][j][1:] = np.maximum(dp[i][j][1:], dp[i][j][:3] + nowv)
#        dp[i][j][3] = max(dp[i][j][3], dp[i][j][2] + nowv)
#        dp[i][j][2] = max(dp[i][j][2], dp[i][j][1] + nowv)
#        dp[i][j][1] = max(dp[i][j][1], dp[i][j][0] + nowv)
#
        dp[i+1][j][0] = max(dp[i+1][j][0], max(dp[i][j]))
        dp[i][j+1][:] = np.maximum(dp[i][j+1][:], dp[i][j][:])

#        dp[i][j+1][0] = max(dp[i][j+1][0], dp[i][j][0])
#        dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][1])
#        dp[i][j+1][2] = max(dp[i][j+1][2], dp[i][j][2])
#        dp[i][j+1][3] = max(dp[i][j+1][2], dp[i][j][3])

print(max(dp[r-1][c-1]))


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

r, c, k = map(int, input().split())
itm = [[0]*(c) for _ in range(r)]
for i in range(k):
    ri, ci, vi = map(int, input().split())
    itm[ri-1][ci-1] = vi

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

print(max(dp1[c-1]))