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

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

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

mod = 10 ** 9 + 7

fac = [1]
inv = [1]
for i in range(1, N + 5) :
  fac.append(fac[-1] * i)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

def dfs(cur, pre=-1) :
  for nex in vec[cur] :
    if nex == pre : continue
    dfs(nex, cur)
    pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
    pattern[cur] %= mod
    subtree[cur] += subtree[nex]
  subtree[cur] += 1
  
dfs(0)

q = [(0, -1, 1)]
while q :
  cur, pre, cp = q.pop()
  pattern[cur] *= cp * comb(N - 1, subtree[cur] - 1)
  pattern[cur] %= mod
  for nex in vec[cur] :
    if nex == pre : continue
    ncp = pattern[cur] * pow(pattern[nex] * comb(N - 1, subtree[nex]), mod - 2, mod) % mod
    q.append((nex, cur, ncp))
  
for i in range(N) :
  print(pattern[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

fac = [1]
for i in range(1, N + 1) :
  fac.append(fac[-1] * i % mod)

inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

# DFS
stack = [(0, -1, 0)]
while stack :
  cur, pre, op = stack.pop()
  
  if op == 0 :
    stack.append((cur, pre, 1))
    for nex in vec[cur] :
      if nex == pre : continue
      stack.append((nex, cur, 0))
  else :
    for nex in vec[cur] :
      pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
      pattern[cur] %= mod
      subtree[cur] += subtree[nex]
    subtree[cur] += 1

# BFS
queue = [(0, -1)]
while queue :
  cur, pre = queue.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    queue.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
mod = pow(10, 9) + 7
K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += comb(i+n-1, n-1) * pow(25, i) * pow(26, (K-i))
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    uf = UnionFind(N)

    for ab in AB:
        uf.union(ab[0]-1, ab[1]-1)

    g = uf.all_group_members()

    ans = 0
    for gg in g:
        if len(g[gg]) > ans:
            ans = len(g[gg])

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    uf = UnionFind(N)

    for ab in AB:
        uf.union(ab[0]-1, ab[1]-1)

    ans = 0
    for i in range(N):
        if uf.size(i) > ans:
            ans = uf.size(i)

    print(ans)


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

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
a0,a1= np.unique(a,return_counts=True)
suma=np.sum(a)
#print(suma)
#print(a0)
#print(a1)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  sumb=a1[np.where(a0==b)]
  a0=np.where(a0==b,c,a0)
  #sumc=0
  #print(a0)
  #print(a1)
  sumc=np.sum(sumb)
  if sumc ==None :
    sumc=0
  #print(sumc)
  sumc*=(c-b)
  #print(sumc)
  suma+=sumc
  print(suma)

### FIXED CODE ###

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
a0,a1= np.unique(a,return_counts=True)
suma=np.sum(a)
a2=np.array([0]*100001)
for j in range(a0.size):
  a2[a0[j]]=a1[j]
#print(suma)
#print(a0)
#print(a1)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  sumb=a2[b]
  a2[b]=0
  a2[c]+=sumb
  sumc=sumb*(c-b)
  suma+=sumc
  print(suma)
### BUGGY CODE ###

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

pairs = []
pairnum = 0
for i in range(N - 2):
    if(C[i + 1] == C[i]):
#        print("col = {} : [{} - {}] : same -> skip".format(C[i], i, i + 1))
        continue
    prev = 0
    for j in range(i + 2, N):
#        print("C[{}] = {}, C[{}] = {}".format(i, C[i], j, C[j]))
        if(prev == C[j]):
            continue
        if(C[j] == C[i]):
#            print("col = {} : [{} - {}]".format(C[i], i, j))
            pairs.append([i, j])
            pairnum = pairnum + 1
        prev = C[j]
#print(str(pairs))

ans = 0
for i in range(1, 2 ** pairnum):
    lastidx = -1
    nocount = 0
#    print("check pair pattern = " + hex(i))
    for j in range(pairnum):
#        print("last idx = {}".format(lastidx))
        if(1 == ((i >> j) & 1)):
            if(lastidx >= pairs[j][0]):
                nocount = 1
                break
            else:
                lastidx = pairs[j][1]
    if(0 == nocount):
        ans = ans + 1
#        print("add pair pattern = " + hex(i))
ans = ans + 1
print(ans % (10 ** 9 + 7))


### FIXED CODE ###

sums = [1]  # pair number sum until index
csums = {}  # pair number sum of each color

N = int(input())
C = []      # color stone list
lastc = -1  # last color of input
for i in range(N):
    c = int(input())
    if(lastc == c):
        continue
    lastc = c
    C.append(c)

#print("C = " + str(C))

for i, c in enumerate(C, 1):
    if(c in csums):
        sums.append(sums[-1] + csums[c])
        csums[c] += sums[i - 1]
    else:
        sums.append(sums[-1])
        csums[c] = sums[i - 1]

#    print("i = {}, c = {}".format(i, c))
#    print("csums = " + str(csums))
#    print("sums = " + str(sums))

print(sums[-1] % (10 ** 9 + 7))
### BUGGY CODE ###

#https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_c

N = int(input())
S = str(input())
Sarray = list(S)
Sarraynum = []

#白0
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        Sarraynum.append(0)
    else:
        Sarraynum.append(1)

a = 2 * len(Sarraynum)
for i in range(len(Sarraynum)):
    black2white = 0
    white2black = 0
    for j in range(i):
        black2white += Sarraynum[j]
        if black2white >= a:
            break

    for j in range(i + 1, len(Sarraynum)):
        if Sarraynum[j] == 0:
            white2black += 1
        if black2white + white2black >= a:
            break
    
    if black2white + white2black < a:
        a = black2white + white2black


print(a)

### FIXED CODE ###

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

white = 0 #にしなきゃ
black = 0 #にしなきゃ
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        black += 1

a = [white + black]
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        black -= 1
    else:
        white += 1
    a.append(white + black)
a.sort()
print(a[0])
### BUGGY CODE ###

n = int(input())
s = [sorted(input()) for _ in range(n)]
ans = 0

for i in range(n):
	for k in range(n):
		if s[i] == s[k] :
			ans += 1

print(int((ans - n) / 2))

### FIXED CODE ###

n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
ans = 0
s_dic = {i:0 for i in s}

for j in range(n):
	if s[j] in s_dic :
		s_dic[s[j]] += 1

print(sum(s_dic[k] * (s_dic[k] - 1) // 2 for k in s_dic))
### BUGGY CODE ###

n,m=map(int,input().split())
w=[]
for i in range(n):
  w.append(list(map(int,input().split())))

w=sorted(w)
#print(w)

total=0
for i in range(m,-1,-1):
#  print("i:"+str(i))
  max=0
  max_j=0
  found=False
  for j in range(len(w)):
    if (m-i)<w[j][0]: #残り日数(m-i)よりも大きい
#      print("残り日数:"+str(m-i) + "　仕事日数:"+str(w[j][0]))
      break
    elif max < w[j][1]:
#      print("最大値:"+str(w[j][1]) + " 添え字:"+str(j))
      max=w[j][1]
      max_j=j
      found=True
#  print(str(max) + "の仕事をやる")
  total = total + max
  if found:
#    print(str(max_j)+"番目の仕事を削除")
    w.pop(max_j)
#    print(w)
      
      
print(total)


### FIXED CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
result = 0
pos = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]
for i in range(N):
    for j in range(M):
        num = 0
        for p in pos:
            i_dest = i + p[0]
            j_dest = j + p[1]
            if 0 <= i_dest < N and 0 <= j_dest < M:
                num += 1
        if num % 2 != 0:
            result += 1
print(result)


### FIXED CODE ###

N, M = list(map(int, input().split()))
result = 0
if N == 1 and M == 1:
    result = 1
elif N == 1:
    result = M - 2
elif M == 1:
    result = N - 2
else:
    result = (N - 2) * (M - 2)
print(result)
### BUGGY CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    mod = 10**9 + 7
    return (x * y) // fractions.gcd(x, y) 

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())

mod = 10**9 + 7

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

num = lcm_list(A)

ans = 0
for i in range(N):
    ans += num // A[i]
    ans %= mod
print(ans)  

### FIXED CODE ###

def gcd(a, b):
    while b!= 0:
        a,b = b, a%b
    return a
def lcm(a,b):
    return a*b //(gcd(a, b))

N = int(input())
A = list(map(int, input().split()))
a_lcm = A[0]

mod = 10 ** 9 + 7

for i in range(1,N):
    a_lcm = lcm(a_lcm, A[i])

ans = 0
for i in range(N):
    ans += a_lcm*pow(A[i], mod-2, mod)
print(ans%mod)
### BUGGY CODE ###

S = input()
ans_l = [0 for _ in range(len(S))]
for i in range(len(S)):
    if(S[i]=="R"):
        j = 0
        while(S[i+j]=="R"):
            j += 1
        if(j%2==1):
            ans_l[i+j-1]+=1
        else:
            ans_l[i+j]+=1

    if(S[i]=="L"):
        j = 0
        while(S[i-j]=="L"):
            j += 1
        if(j%2==1):
            ans_l[i-j+1]+=1
        else:
            ans_l[i-j]+=1

print(" ".join(map(str,ans_l)))



### FIXED CODE ###

S = input()
ans_l = [0 for _ in range(len(S))]

"""
for i in range(len(S)):
    if(S[i]=="R"):
        j = 0
        while(S[i+j]=="R"):
            j += 1
        if(j%2==1):
            ans_l[i+j-1]+=1
        else:
            ans_l[i+j]+=1

    if(S[i]=="L"):
        j = 0
        while(S[i-j]=="L"):
            j += 1
        if(j%2==1):
            ans_l[i-j+1]+=1
        else:
            ans_l[i-j]+=1
"""
i =0
while(i<len(S)):
    j=0
    while(S[i+j]=="R"):
        j += 1
    k=0
    while(S[i+j+k]=="L"):
        k += 1
        if(i+j+k>=len(S)):
            break
    ans_l[i+j-1] += j//2+ k//2 + j%2
    ans_l[i+j] += j//2 + k//2 + k%2
    i += j+k


print(" ".join(map(str,ans_l)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=list(map(int,input().split()))
B=list(map(int, input().split()))
ans=0
for k in range(29):
    A_k,B_k=[[],[]],[[],[]]
    for ai in A:
        A_k[(ai&(1<<k))>>k].append(ai)
    for bi in B:
        B_k[(bi&(1<<k))>>k].append(bi)
    A,B=[],[]
    for i in range(2):
        A+=A_k[i]
        B+=B_k[i]
    mod=1<<(k+1)
    A_mod=[ai%mod for ai in A]
    B_mod=[bi%mod for bi in B]
    t=1<<k
    S=[n]*4
    cnt=0
    for ai in A_mod:
        Border=[t-ai,t*2-ai,t*3-ai,t*4-ai]
        for i in range(4):
            while 0<S[i] and Border[i]<=B_mod[S[i]-1]:
                S[i]-=1            
        cnt+=((S[1]-S[0])+(S[3]-S[2]))
    if cnt&1:
        ans+=t
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=list(map(int,input().split()))
B=list(map(int, input().split()))
ans=0
for k in range(29):
    A_k,B_k=[[],[]],[[],[]]
    for ai in A:
        A_k[(ai&(1<<k))>>k].append(ai)
    for bi in B:
        B_k[(bi&(1<<k))>>k].append(bi)
    A,B=[],[]
    for i in range(2):
        A+=A_k[i]
        B+=B_k[i]
    mod=1<<(k+1)
    A_mod=[ai%mod for ai in A]
    B_mod=[bi%mod for bi in B]
    t=1<<k
    S=[n]*4
    cnt=0
    for ai in A_mod:
        Border=[t-ai,t*2-ai,t*3-ai,t*4-ai]
        for i in range(4):
            while 0<S[i] and Border[i]<=B_mod[S[i]-1]:
                S[i]-=1            
        cnt+=((S[1]-S[0])+(S[3]-S[2]))
    if cnt&1:
        ans+=t
print(ans)
### BUGGY CODE ###

import math

A,B,Q = map(int, input().split())
S=[0]*A
T=[0]*B
for i in range(A):
  S[i] = int(input())
for i in range(B):
  T[i] = int(input())
S.append(10**11)
S.insert(0,(-1)*(10**11))
T.append(10**11)
T.insert(0,(-1)*(10**11))
for i in range(Q):
  x = int(input())
  floor = 0
  ceil = len(S)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    s = S[half]
    if s < x:
      floor = half
    elif x < s:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_S = [S[floor]-x, S[ceil]-x]
        
  floor = 0
  ceil = len(T)-1
  while ceil-floor > 1:
    half = math.floor((floor+ceil)/2)
    t = T[half]
    if t < x:
      floor = half
    elif x < t:
      ceil = half
    else:
      floor = half
      ceil = half+1
  nearest_x_T = [T[floor]-x, T[ceil]-x]
  
  ans_cand = []
  for x_S in nearest_x_S:
    for x_T in nearest_x_T:
      if x_S*x_T > 0:
        ans_cand.append(max(abs(x_S),abs(x_T)))
      else:
        ans_cand.append(abs(x_S)+abs(x_T)+min(abs(x_S),abs(x_T)))
  print(int(min(ans_cand)))
  
  


### FIXED CODE ###

mod = 1000000007
eps = 10**-9
inf = 10**15


def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    A, B, Q = map(int, input().split())
    S = [-inf]
    for _ in range(A):
        S.append(int(input()))
    S.append(inf)
    T = [-inf]
    for _ in range(B):
        T.append(int(input()))
    T.append(inf)

    for _ in range(Q):
        x = int(input())
        i = bisect_left(S, x)
        j = bisect_left(T, x)
        ans = []
        ans.append(x - S[i-1] + abs(S[i-1] - T[j-1]))
        ans.append(x - S[i-1] + abs(S[i-1] - T[j]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i-1]))
        ans.append(x - T[j-1] + abs(T[j-1] - S[i]))
        ans.append(S[i] - x + abs(S[i] - T[j-1]))
        ans.append(S[i] - x + abs(S[i] - T[j]))
        ans.append(T[j] - x + abs(T[j] - S[i-1]))
        ans.append(T[j] - x + abs(T[j] - S[i]))
        print(min(ans))


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

s = input()
t = input()

for i in range(len(s)):
    if s[i] == t[i]:
        continue
    else:
        s = s.translate(str.maketrans({s[i]: t[i], t[i]: s[i]}))
if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()
s_memo = {}
t_memo = {}

for i in range(len(s)):
    c1 = s[i]
    c2 = t[i]
    if (c1 in s_memo and s_memo[c1] != c2) or \
            (c2 in t_memo and t_memo[c2] != c1):
        print("No")
        exit()
    s_memo[c1] = c2
    t_memo[c2] = c1

print("Yes")
### BUGGY CODE ###

import itertools
n=int(input())
S=[]
C=['M','A','R','C','H']
for i in range(n):
    x=input()
    if x[0] in C:
        S.append(x)

X=list(itertools.combinations(S,3))
res=len(X)
for i in range(len(X)):
    Y=[X[i][0][0],X[i][1][0],X[i][2][0]]
    if len(set(Y))<3:
        res-=1

print(res)

### FIXED CODE ###

import itertools
n=int(input())
D={'M':0,'A':0,'R':0,'C':0,'H':0}
for i in range(n):
    x=input()
    if x[0]=='M':
        D['M']+=1
    elif x[0]=='A':
        D['A']+=1
    elif x[0]=='R':
        D['R']+=1
    elif x[0]=='C':
        D['C']+=1
    elif x[0]=='H':
        D['H']+=1

X=D.values()
Y=list(itertools.combinations(X,3))
cnt=0
for i in range(10):
    cnt+=Y[i][0]*Y[i][1]*Y[i][2]

print(cnt)
### BUGGY CODE ###

import copy
R, C, K = map(int,input().split())
i = [list(map(int,input().split())) for k in range(K)]
dp0 = []
for r in range(R):
   dp0.append([])
   for c in range(C):
      dp0[r].append([])
      dp0[r][c] = 0
location = copy.deepcopy(dp0)
dp1 = copy.deepcopy(dp0)
dp2 = copy.deepcopy(dp0)
dp3 = copy.deepcopy(dp0)
for k in range(K):
   location[i[k][0]-1][i[k][1]-1] = i[k][2]
dp1[0][0] = location[0][0]
if R > 1:
   for r in range(R-1):
      dp1[r+1][0] = location[r+1][0] + dp1[r][0]
      dp0[r+1][0] = dp1[r][0]
if C > 1:
   for c in range(C-1):
      dp0[0][c+1] = dp0[0][c]
      dp1[0][c+1] = max(location[0][c+1] + dp0[0][c], dp1[0][c])
      dp2[0][c+1] = max(location[0][c+1] + dp1[0][c], dp2[0][c])
      dp3[0][c+1] = max(location[0][c+1] + dp2[0][c], dp3[0][c])
   if R > 1:
      for r in range(R-1):
         for c in range(C-1):
            dp0[r+1][c+1] = max(dp0[r+1][c], dp0[r][c+1], dp1[r][c+1], dp2[r][c+1], dp3[r][c+1])
            dp1[r+1][c+1] = max(dp0[r+1][c+1] + location[r+1][c+1], dp1[r+1][c])
            dp2[r+1][c+1] = max(dp1[r+1][c] + location[r+1][c+1], dp2[r+1][c])
            dp3[r+1][c+1] = max(dp2[r+1][c] + location[r+1][c+1], dp3[r+1][c])
if R==1 and C==1:
   ans = i[-1][-1]
else:
   ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)

### FIXED CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
### BUGGY CODE ###

R, G, B, n = map(int, input().split())
cnt = 0
for r in range(int(n//R)+1):
  for g in range(int(n//G)+1):
    
      if (n - (r*R + g*G)) % B == 0 and n - (r*R + g*G) >= 0:
        
        cnt +=1
print(cnt)

### FIXED CODE ###

R, G, B, n = map(int, input().split())
cnt = 0
for r in range((n//R)+1):
  for g in range((n//G)+1):
    
      if (n - (r*R + g*G)) % B == 0 and n - (r*R + g*G) >= 0:
        
        cnt +=1
print(cnt)
### BUGGY CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
sub=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+(j-i)
        if s[i]==s[j]:
            continue
        if k>=n or s[i]==s[k] or s[j]==s[k]:
            continue
        sub+=1
print(ans-sub)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in range(n):
    if s[i]=="R":
        r+=1
    elif s[i]=="G":
        g+=1
    else:
        b+=1
ans=r*g*b
sub=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+(j-i)
        if s[i]==s[j]:
            continue
        if k>=n or s[i]==s[k] or s[j]==s[k]:
            continue
        sub+=1
print(ans-sub)
### BUGGY CODE ###

R,G,B,N = list(map(int, input().split()))
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        now = N - r*R - g*G
        if  now >= 0 and now % B == 0:
            ans += 1
print(ans)


### FIXED CODE ###

R,G,B,N = list(map(int, input().split()))
ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        now = N - r*R - g*G
        if  now >= 0 and now % B == 0:
            ans += 1
print(ans)