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

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

### FIXED CODE ###

import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            q=queue.Queue()
            d=0
            q.put([i,j])
            x[i][j]=0
            while q.qsize()!=0:
                d+=1
                l=q.qsize()
                for t in range(l):
                    I,J=q.get()
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))
### BUGGY CODE ###


N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
ans = 0
for i in range(N - 1):
  for j in range(i+1, N):
    a = A[i] % mod
    b = A[j] % mod
    ans += a * b
    ans = ans % mod

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
ans = 0
#TLE
'''
for i in range(N - 1):
  for j in range(i+1, N):
    a = A[i] % mod
    b = A[j] % mod
    ans += (a * b) % mod
    ans = ans % mod
'''
tot = 0
for i in range(N):
  A[i] %= mod
  tot += A[i]
  tot %= mod
for i in range(N-1):
  tot -= A[i]
  ans += (A[i] * tot) % mod
  ans %= mod
print(ans)
### BUGGY CODE ###

MOD=998244353
N=int(input())
A=[int(input()) for _ in range(N)]

TOTAL=pow(3,N,MOD)
ASum=sum(A)
AMax=max(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]

dp[0][0] = 2
dp[0][A[0]] = 1

prev=0
current=1
for n in range(1,N):
	current = n % 2
	prev = (n+1) % 2
	for e in range(ASum+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD
sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= MOD
	plus = (dpOther[ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )



### FIXED CODE ###

import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )
### BUGGY CODE ###

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

### FIXED CODE ###

import math
K=int(input())
ans=0
for i in range(1,K+1):
    ans += i

for i in range(1,K):
    for j in range(i+1,K+1):
        ans += math.gcd(i,j)*6
        
for i in range(1,K-1):
    for j in range(i+1,K):
        for k in range(j+1,K+1):
            ans += math.gcd(i,math.gcd(j,k))*6
print(ans)
### BUGGY CODE ###

import copy

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了


#l_blackの設定
l_black = []
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]


#探索
cnt = 0

while len(l_black) > 0:

  l_change = []

  #vは黒マスリスト #新たに黒マスになる白マスの座標をl_changeに詰めていく
  for v in l_black:
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標をl_changeに追加
      if grid[i[0]][i[1]] == ".":
        l_change.append( i )
  
  #l_changeの中の白マスを黒にする
  for i in l_change:
    grid[i[0]][i[1]] = "#" 
  #l_blackの中を新たに黒鱒になったやつの座標だけにする
  l_black = copy.deepcopy( l_change )
  if len(l_black) > 0:
    cnt = cnt + 1
print(cnt)  

### FIXED CODE ###

import copy
from collections import deque

####入力
H,W = map(int,input().split())

#gridの定義
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
####入力終了

#distの設定
dist = [[0 for i in range(W)] for j in range(H)]

#l_blackの設定
l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "#":
      l_black.append( [i,j] ) # [行,列]

#探索
max_d = 0

while len(l_black) > 0:
  #vは黒マスの座標 
  while len(l_black) > 0:
    v = l_black.popleft()
    #iはvの上下左右のマスの座標[行,列]
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      #場外アウトの場合はスルー
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      #移動先がもう黒マスの場合スルー
      if grid[i[0]][i[1]] == "#":
        continue
      #移動先が白マスならばそこの座標を黒マスにして距離を記録する
      if grid[i[0]][i[1]] == ".":
        #黒マスにする
        grid[i[0]][i[1]] = "#"
        #新たに黒鱒となった座標をl_blackに追加
        l_black.append(i)
        #距離の記録
        dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
        max_d = max(max_d,dist[i[0]][i[1]])
print(max_d)
### BUGGY CODE ###

import sys


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

    imps = sys.stdin.readlines()

    db = []
    for imp in imps:
        command = imp.split(' ')
        if command[0] == 'insert':
            db.append(command[1])
        elif command[0] == 'find':
            if command[1] in db:
                print('yes')
            else:
                print('no')


main()

### FIXED CODE ###

import sys


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

    imps = sys.stdin.readlines()

    db = {}
    for imp in imps:
        c, k = imp.split(' ')
        if c == 'insert':
            db[k] = 0
        elif k in db:
            print('yes')
        else:
            print('no')


main()
### BUGGY CODE ###

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

X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x

que=[(0,X[0])]
done=[-1]*N
while len(que)>0:
    t=que.pop(0)
    now, count=t
    X[now]=count
    done[now]=1
    for nex in G[now]:
        if done[nex]!=-1:
            continue
        else:
            que.append((nex, count+X[nex]))

print(*X)

### FIXED CODE ###

from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

N,K=map(int,input().split())
count=0
for a in range(1,N+1):
  for b in range(1,N+1):
    for c in range(1,N+1):
      if 2*(a+b+c)%K==0:
        if (a+b)%K==0 and (b+c)%K==0 and (c+a)%K==0:
          count+=1
print(count)


### FIXED CODE ###

n,k=map(int,input().split())
ans=0
if k%2==0:
  ans+=(n//k+(1 if n%k>=k//2 else 0))**3
ans+=(n//k)**3
print(ans)
### BUGGY CODE ###

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

arr = [abs(sum(a[:i]) - sum(a[i:]))  for i in range(1,N)]

print(min(arr))

### FIXED CODE ###

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

S = sum(a)
_min  = 10000000000000000000
x = 0
for i in range(0,N-1):
  x += a[i]
  tmp = abs(S - 2*x)
  if tmp < _min:
    _min = tmp

print(_min)
### BUGGY CODE ###

import sys

x = raw_input()

x = [i for i in x]

while(True):
    end = True
    for i in range(0,len(x)-1):
#        print len(x),i,x[i],x[i+1],end
        if(x[i]=='S' and x[i+1]=='T'):
            del x[i+1]
            del x[i]
            end = False
#            print x
        if end is False:
            break

    if end:
        print len(x)
        sys.exit()

### FIXED CODE ###

x = raw_input()

l = len(x)

s = 0
for i in x:
    if(i=='S'): s+=1
    if(i=='T' and s>0): 
        s-=1
        l-=2

print l
### BUGGY CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    eval = []
    tmp = 1

    for i in range(N):
        tmp *= A[i]

        if i >= K - 1:
            eval.append(tmp)
            tmp //= A[i-(K-1)]
    
    for i in range(1, len(eval)):
        if eval[i] > eval[i-1]:
            print('Yes')
        else:
            print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    for i in range(N-K):
        if A[i] < A[i+K]:
            print('Yes')
        else:
            print('No')

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

def main():
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		this_gcd = A[i-1] if i > 0 else A[i+1]
		for j in range(N):
			if i == j:
				continue
			this_gcd = gcd(this_gcd, A[j])
		ans = max(ans, this_gcd)
	print(ans)


def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	c = a % b
	return gcd(b, c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	dp_l = [0]*(N+2)
	dp_r = [0]*(N+2)

	for i in range(N):
		dp_l[i+1] = gcd(dp_l[i], A[i])

	for i in range(N-1, 0, -1):
		dp_r[i] = gcd(dp_r[i+1], A[i])

	ans = 1
	for i in range(1, N+1):
		this_ans=gcd(dp_l[i-1], dp_r[i])
		ans = max(ans, this_ans)

	print(ans)



def gcd(a, b):
	if a < b:
		a, b = b, a
	if b == 0:
		return a
	c = a % b
	return gcd(b, c)

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

from collections import deque
s=str(input())

q=int(input())
for i in range(q):
    a=input().strip()
    a=list(a)
    #print(a)
    if int(a[0])==1:
        #print("DFGHJ")
        s=s[::-1]
    if int(a[0])==2:
        #print(a[2])
        s=list(s)
        if int(a[2])==1:
            s=deque(s)
            #print(s)
            s.appendleft(str(a[4]))
            #print(s)
            s=list(s)
            #print("DFGH",s)
        else:
            s.append(str(a[4]))
        s=''.join(s)
        #print(s)        
print(s)


### FIXED CODE ###

from collections import deque
s=str(input())

front = ""
back = ""#前と後ろに分ける最後につなげてリバース

now_swap = 0
q=int(input())
for i in range(q):
    a = input().strip()
    a = list(a)
    
    if a[0] == "1":
        if now_swap == 0:
           now_swap = 1
        else: #now_step == 1:
            now_swap = 0
    else:
        if now_swap == 1:
            if a[2] == "1":
               # print("back")
                back+=a[4]

            else: #a[1]==2:
               ## print("f 2")
                front = a[4] + front

        else: #now_step == 0:
            if a[2] == "1":
                front = a[4] + front

            else: #a[1]==2:
                #print("hj")
                back+=a[4]
ans= front + s + back
#print(front,a,back)
if now_swap == 1:#合計数が奇数なら
    
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
lis = []
for i in range(M):
    B ,C = map(int, input().split())
    for j in range(B):
        A.append(C)
A.sort(reverse=True)
ans = 0
for i in range(N):
    ans += A[i]
print(ans)


### FIXED CODE ###

from operator import itemgetter
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
BC_list = []
BC_sorted = sorted(BC,key=itemgetter(1) ,reverse = True)

for i in BC_sorted:
    BC_list += [i[1]] * i[0]
    if len(BC_list) > N:
        break

Answer = 0
A += BC_list
ALL = sorted(A, reverse = True)

for i in range(N):
    Answer += ALL[i]
print(Answer)
### BUGGY CODE ###

import collections
n = int(input())
s = []
for i in range(n):
    s.append(input())

c = collections.Counter(s)
keys = list(c.keys())
values = list(c.values())
ans = []
for i,v in enumerate(values):
    if v == max(values):
        ans.append(keys[i])
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
c = Counter(s)
m = 0
for v in c.values():
	m = max(m, v)
ans = []
for k, v in c.items():
	if v == m:
		ans.append(k)
ans.sort()
print(*ans, sep="\n")
### BUGGY CODE ###

import bisect

a,b,q=map(int,input().split())
s = []
t = []
for i in range(a):
  s.append(int(input()))
for i in range(b):
  t.append(int(input()))
for _ in range(q):
  x = int(input())
  
  ans = [0,0,0]
  
  if x in s:
    sl = 0
    sr = 0
  else:
    i = bisect.bisect_left(s,x)
    if i == 0:
      sl = 100000000000
    else:
      sl = abs(s[i-1]-x)
    if i == a:
      sr = 100000000000
    else:
      sr = abs(s[i]-x)
  if x in t:
    tl = 0
    tr = 0
  else:
    i = bisect.bisect_left(t,x)
    if i == 0:
      tl = 100000000000
    else:
      tl = abs(t[i-1]-x)
    if i == b:
      tr = 100000000000
    else:
      tr = abs(t[i]-x)
  ans[0] = max(tl,sl)
  ans[1] = max(tr,sr)
  ans[2] = min(2*tl+sr,2*sl+tr,2*sr+tl,2*tr+sl)
  print(min(ans))

### FIXED CODE ###

import bisect

a,b,q=map(int,input().split())
s = []
t = []
for i in range(a):
  s.append(int(input()))
for i in range(b):
  t.append(int(input()))
for _ in range(q):
  x = int(input())
  
  ans = [0,0,0]
  
  i = bisect.bisect_left(s,x)
  if i == 0:
    sl = 100000000000
  else:
    sl = abs(s[i-1]-x)
  if i == a:
    sr = 100000000000
  else:
    sr = abs(s[i]-x)
  i = bisect.bisect_left(t,x)
  if i == 0:
    tl = 100000000000
  else:
    tl = abs(t[i-1]-x)
  if i == b:
    tr = 100000000000
  else:
    tr = abs(t[i]-x)
  ans[0] = max(tl,sl)
  ans[1] = max(tr,sr)
  ans[2] = min(2*tl+sr,2*sl+tr,2*sr+tl,2*tr+sl)
  print(min(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import numpy as np

s = str(input())

mod = 2019

div_memo = []
for i in range(1, len(s)+1):
    # print(s[len(s)-i:])
    div_memo.append(int(s[len(s)-i:]) % mod)

u, counts = np.unique(div_memo, return_counts=True)

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

if u[0] == 0:
    ans += counts[0]
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

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

ans += div_memo[0]
print(int(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
INF = float('inf')
p = 2 ** N
dp = [INF] * p
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])
    for i in range(p):
        dp[i | c] = min(dp[i] + a, dp[i | c])

if dp[-1] != INF:
    print(dp[-1])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
INF = 10 ** 10
p = 2 ** N
dp = [INF] * p
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])
    for i in range(p):
        dp[i | c] = min(dp[i] + a, dp[i | c])

if dp[-1] != INF:
    print(dp[-1])
else:
    print(-1)
### BUGGY CODE ###

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

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

  Q=int(input())
  for q in range(Q):
    l,r=map(int,input().split())
    t,i=0,~-l  
    for j in range((r-l)//D):
      t+=abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D
    print(t)

main()


### FIXED CODE ###

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

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

  B=[0]*(H*W)
  for i in range(D):
    while i+D<W*H:
      B[i+D]=B[i]+abs(A[i][1]-A[i+D][1])+abs(A[i][2]-A[i+D][2])
      i+=D

  for q in range(int(input())):
    l,r=map(int,input().split())
    print(B[~-r]-B[~-l])

main()
### BUGGY CODE ###

import numpy as np

K=int(input())

S=0
for a in range(1,K+1):
    for b in range(1,K+1):
        calc=np.gcd(a,b)
        for c in range(1,K+1):
            if(c%calc==0):
                S+=calc
            else:
                S+=np.gcd(calc,c)

print(S)

### FIXED CODE ###

from math import gcd
 
K=int(input())
 
S=0
for a in range(1,K+1):
    for b in range(1,K+1):
        calc=gcd(a,b)
        for c in range(1,K+1):
                S+=gcd(calc,c)
 
print(S)
### BUGGY CODE ###

s = input()
q = int(input())
query = [input() for i in range(q)]

for i in range(q):
  temp = query[i].split()
  if int(temp[0]) == 1:
    s = s[::-1]
  else:
    if int(temp[1]) == 1:
      s = '{}{}'.format(temp[2], s)
    else:
      s = '{}{}'.format(s, temp[2])

print(s)


### FIXED CODE ###

from collections import deque

def main():
  rev = False
  s = deque(input())
  q = int(input())
  query = tuple(input() for i in range(q))

  for i in range(q):
    temp = query[i].split()
    if int(temp[0]) == 1:
      rev = not rev
    else:
      if (int(temp[1]) == 1 and (not rev)) or (int(temp[1]) == 2 and rev):
        s.appendleft(temp[2])
      else:
        s.append(temp[2])

  if rev:
    s.reverse()

  print(''.join(s))

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

import functools
A, B = map(int, input().split())
print(functools.reduce(lambda x, y: x^y, range(A, B+1)))

### FIXED CODE ###

A, B = map(int, input().split())
print([A-1, 1, A, 0][(A-1)%4]^[B, 1, B+1, 0][B%4])
### BUGGY CODE ###

from collections import defaultdict
R, C, K = map(int, input().split())
dp = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = defaultdict(int)

for i in range(R):
    for j in range(C):
        D[(i, j)] = 0

for i in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] += v

for i in range(R+1):
    for j in range(C+1):
        if i==0 and j==0: continue
        if D[(i, j)] > 0:
            v = D[(i, j)]
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = max(dp[i][j-1][0]+v, dp[i][j-1][1], M+v)
            dp[i][j][2] = max(dp[i][j-1][1]+v, dp[i][j-1][2])
            dp[i][j][3] = max(dp[i][j-1][2]+v, dp[i][j-1][3])

        elif D[(i, j)] == 0:
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = dp[i][j-1][1]
            dp[i][j][2] = dp[i][j-1][2]
            dp[i][j][3] = dp[i][j-1][3]

ans = 0
for i in range(4):
    ans = max(ans, dp[-1][-1][i])
print(ans)

### FIXED CODE ###

R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

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

mem = {}
def rec(arr):
    if len(arr)==1:
        if arr[0] == 1:
            return [1]
        else:
            return False
    h = hash(tuple(arr))
    if h in mem:
        return mem[h]
    for i,a in reversed(list(enumerate(arr))):
        if i+1 == a:
            _arr = arr[:]
            del _arr[i]
            res = rec(_arr)
            if res:
                res.append(i+1)
                mem[h] = res
                break
    else:
        mem[h] = False
    return mem[h]

ans = rec(B)
if ans:
    print(*ans,sep='\n')
else:
    print(-1)

### FIXED CODE ###

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

ans = []
while B:
    for i,a in reversed(list(enumerate(B))):
        if i+1 == a:
            ans.append(a)
            del B[i]
            break
    else:
        print(-1)
        exit()
print(*ans[::-1], sep='\n')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
  	print(0)
  	exit()
for i in A:
    ans = ans * i
if ans > pow(10, 18):
    print(-1)
    exit()
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
    exit(0)
ans = 1
for i in A:
    ans = ans * i
    if ans > pow(10, 18):
        print(-1)
        exit(0)
else:
    print(ans)
### BUGGY CODE ###

import sys
#DEBUG=True
DEBUG=False
num=7
if DEBUG:
    f=open("C_input.txt")
else:
    f=sys.stdin
N=int(f.readline().strip())
mod_sum=0
ind=1
pdt=1
if N%2==0:
    print("-1")
else:
    mod_sum=num%N
    if not mod_sum:
        print(ind)
    else:
        while True:
            pdt*=10
            tmp=(num*pdt)%N
            mod_sum=(mod_sum+tmp)%N
            ind+=1
            if not mod_sum:
                print(ind)
                break
f.close()

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("C_input.txt")
else:
    f=sys.stdin
mod=1
ans=0
N=int(f.readline().strip())
if N%2==0 or N%5==0:
    print("-1")
else:
    if N%7==0:
        A=N*9/7
    else:
        A=N*9
    while True:
        ans+=1
        mod=(10*mod)%A
        if mod==1:
            print(ans)
            break
f.close()