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

import numpy as np
def min_rounte(s, sta, path):
    move = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in move:
        ax = [sta[0]+i[0], sta[1]+i[1]]
        if s[ax[0]][ax[1]] == -1:
            continue
        if s[ax[0]][ax[1]] > path:
            s[ax[0]][ax[1]] = path
    return s
 
def bfs(s, sta):
    s_ = np.array(s)
    s_[sta[0]][sta[1]] = 0
    for i in range(400):
        ind = np.where(s_==i)
        for j in range(len(ind[0])):
            s_ = min_rounte(s_, [ind[0][j], ind[1][j]], i+1)
        if len(ind[0]) == 0:
            break
    return i-1
        

h, w = map(int, input().split())
#s_ = [[0 if i=="." else -1 for i in input()] for j in range(h)]
s = [[-1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == ".":
            s[i+1][j+1] = 512
        else:
            s[i+1][j+1] = -1
  
ans = 1

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == -1:
            continue
        temp = bfs(s, [i,j])
        if temp > ans:
            ans = temp
print(ans)

### FIXED CODE ###

import numpy as np
def min_rounte(s, sta, path):
    move = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in move:
        ax = [sta[0]+i[0], sta[1]+i[1]]
        if s[ax[0]][ax[1]] == -1:
            continue
        if s[ax[0]][ax[1]] > path:
            s[ax[0]][ax[1]] = path
    return s
 
def bfs(s, sta):
    s_ = np.array(s)
    s_[sta[0]][sta[1]] = 0
    tmp = sta
    for i in range(400):
        ind = np.where(s_==i)
        for j in range(len(ind[0])):
            s_ = min_rounte(s_, [ind[0][j], ind[1][j]], i+1)
        if len(ind[0]) == 0:
            break
        tmp = [[ind[0][k], ind[1][k]] for k in range(len(ind[0]))]
    return i-1, tmp
        

h, w = map(int, input().split())
#s_ = [[0 if i=="." else -1 for i in input()] for j in range(h)]
s = [[-1 for i in range(w+2)] for j in range(h+2)]
for i in range(h):
    a = input()
    for j in range(w):
        if a[j] == ".":
            s[i+1][j+1] = 512
        else:
            s[i+1][j+1] = -1

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == -1:
            continue
        temp, ax = bfs(s, [i,j])
        break
ans = 1
for i in ax:
    ans_, t = bfs(s, i)
    if ans_ > ans:
        ans = ans_

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

S = list(input())
Q = int(input())
Query = [list(input().split()) for i in range(Q)]

from collections import deque

q = deque(S)

r = 0  #反転の有無

for i in range(Q):
    if Query[i][0] == '1':
        r = 1-r
    else:
        if (r + int(Query[i][1])) % 2 == 1:
            q.appendleft(Query[i][2])
        else:
            q.append(Query[i][2])

A = list(q)

if r % 2 == 1:
    A.reverse()

ans = ''
for i in range(len(A)):
    ans += A[i]

print(ans)

### FIXED CODE ###

S = list(input())
Q = int(input())
Query = [list(input().split()) for i in range(Q)]

from collections import deque

q = deque(S)

r = 0  #反転の有無

for i in range(Q):
    if Query[i][0] == '1':
        r = 1-r
    else:
        if (r + int(Query[i][1])) % 2 == 1:
            q.appendleft(Query[i][2])
        else:
            q.append(Query[i][2])

A = list(q)

if r % 2 == 1:
    A.reverse()

ans = ''
for i in range(len(A)):
    ans += A[i]

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

# coding: utf-8
N,P = list(map(int, input().split()))
S = '0'+input()

dp = [[0 for _ in range(P)] for i in range(N+1)]
mod_tab = [[0 for _ in range(10)] for i in range(P)]

for p in range(P):
    for a in range(10):
        mod_tab[p][a] = (p*10+a)%P

dp[1][int(S[1])%P]=1
for i in range(2,N+1):
    dp[i][int(S[i])%P] += 1
    for p in range(P):
        target = mod_tab[p][int(S[i])]
        dp[i][target] += dp[i-1][p]
sum=0
for i in range(1,N+1):
    sum+=dp[i][0]
print(sum)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N,P = list(map(int, input().split()))
S = '0'+input()

#N=200000
#P=9893
#S= '0'+'1234567890' * 20000

if (P==2)|(P==5):
    sum=0
    for i in range(N, 0, -1):
        if int(S[i]) % P == 0:
            sum+= i
    print(sum)


else:
    dp1 = np.zeros(N + 1)
    dp2 = np.zeros(N + 1)
    dp3 = np.zeros(P)
    dp1[N] = int(S[N]) % P
    dp3[int(dp1[N])] += 1
    k = 1
    for i in range(N - 1, 0, -1):
        dp1[i] = (dp1[i + 1] + (int(S[i]) * 10 * k)) % P
        dp3[int(dp1[i])] += 1
        k = (k * 10) % P

    sum = 0

    for i in range(P):
        if i == 0:
            sum += (dp3[i] * (dp3[i] - 1)) // 2 + dp3[i]
            continue
        if dp3[i] == 0: continue
        sum += (dp3[i] * (dp3[i] - 1)) // 2
    print(int(sum))
### BUGGY CODE ###

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  return result
ans=0
Tlen=H*W
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))

### FIXED CODE ###

import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1
#print(S)
def bfs(sx,sy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    """
    if (p[0]==gx and p[1]==gy):
      break
    """
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  """
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  """
  result=d.max()
  return result
ans=0
Tlen=H*W
for sx in range(H):
  for sy in range(W):
    if S[sx,sy]=="#":
      continue
    res=bfs(sx,sy)
    ans=max(ans, res)
"""
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))
### BUGGY CODE ###

n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+1)
for i in range(1,bitx+1):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
if bitx != 1:
    for i in range(n):
        if x>>(n-i-1)&1:
            xm = x^(1<<(n-i-1))
            xm = xm % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = x%bitp
            xm = (xm + 2**(n-i-1))%bitp
            l.append(str(1+ans[xm]))

else:
    for i in range(n):
        if x>>(n-i-1)&1:
            l.append(str(0))
        else:
            xm = x%bitp
            xm = (xm + 2**(n-i-1))%bitp
            l.append(str(1+ans[xm]))

print('\n'.join(l))



### FIXED CODE ###

n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0


if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
            xmm += pow(2, n-(i+1), bitm)
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
else:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
print('\n'.join(l))
### BUGGY CODE ###

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)


ans = 0
for i in range(N):
    if i == 0:
        B = [A[0]]
        continue
    index, mx = 0, 0
    for j in range(len(B)):
        tmp = min(B[j-1], B[j])
        if mx < tmp:
            mx = tmp
            index = j
    B.insert(index, A[i])
    ans += mx
print(ans)


### FIXED CODE ###

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)


ans = 0
for i in range(N):
    if i == 0:
        continue
    else:
        ans += A[i//2]
print(ans)
### BUGGY CODE ###

import heapq
x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

ri=sorted(r)[::-1]

qi=q[::]
pi=p[::]
if x>a:
    pi+=ri[:x-a]
    ri=ri[x-a:]
if y>b:
    qi+=ri[:y-b]
    ri=ri[y-b:]

pi=sorted(pi)[::-1]
pi=pi[:x]
qi=sorted(qi)[::-1]
qi=qi[:y]
heapq.heapify(pi)
heapq.heapify(qi)

try:
    while pi[0]<ri[0] or qi[0]<ri[0]:
        if pi[0]<qi[0]:
            heapq.heappop(pi)
            heapq.heappush(pi,ri[0])
            ri.pop(0)
        else:
            heapq.heappop(qi)
            heapq.heappush(qi,ri[0])
            ri.pop(0)
except IndexError:
    ri=ri
print(sum(pi)+sum(qi))


### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))

ri=sorted(r)[::-1]

qi=q[::]
pi=p[::]
pi=sorted(pi)[::-1]
pi=pi[:x]
qi=sorted(qi)[::-1]
qi=qi[:y]

l=pi+qi
l=sorted(l)
k=0
for i in range(min(c,x+y)):
    if l[i]>ri[i]:
        break
    else:
        k=i+1
print(sum(l[k:])+sum(ri[:k]))
### BUGGY CODE ###

def f(t):
    return t

s=input()
q=int(input())
queri=[]
rv=0
for i in range(q):
    tmp=list(map(f,input().split()))
    queri.append(tmp)
    if tmp==["1"]:
        rv+=1
rv=rv%2
if rv==1: s=s[::-1]

for i in range(q):
    if queri[i][0]=="2":
        rvt=(rv+int(queri[i][1]))%2
        if rvt==1: s=queri[i][2]+s
        else: s=s+queri[i][2]

    else: rv=(rv+1)%2

print(s)

### FIXED CODE ###

s=input()
q=int(input())
queri=[]
rv=0
forward=[]
back=[]
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward.append(queri[2])
        else: back.append(queri[2])

    else: rv=(rv+1)%2

if rv==0:
    for i in range(len(forward)-1,-1,-1):
        print(forward[i],end="")
    print(s,end="")
    for i in range(len(back)):
        print(back[i],end="")
        
if rv==1:
    for i in range(len(back)-1,-1,-1):
        print(back[i],end="")
    print(s[::-1],end="")
    for i in range(len(forward)):
        print(forward[i],end="")
### BUGGY CODE ###

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

b2=[]
b2.append(0)
for i in range(1,m+1):
  b2.append(b2[i-1]+b[i-1])
a.insert(0,0)
cnt=0
a_sum=0
for i in range(n+1):
  j=m
  a_sum+=a[i]
  while True:
    if k>=a_sum+b2[j]:
      cnt=max(cnt,i+j)
      break
    j-=1
    if j <0:
      break
print(cnt)

### FIXED CODE ###

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

b2=[]
b2.append(0)
for i in range(1,m+1):
  b2.append(b2[i-1]+b[i-1])
a.insert(0,0)
cnt=0
a_sum=0
for i in range(n+1):
  j=m
  a_sum+=a[i]
  while True:
    if k>=a_sum+b2[j]:
      cnt=max(cnt,i+j)
      m=j
      break
    j-=1
    if j <0:
      break
print(cnt)
### BUGGY CODE ###

n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    p.append(tmp)

from collections import defaultdict
d = defaultdict(int)

for tmp in p:
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if nxt in finish:
            pass
        else:
            Q.append([nxt,val])

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

numbers = {'1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 6}

N, M = map(int, input().split())
A = list(input().split())
cands = [(a, numbers[a]) for a in A]

dp = {i: None for i in range(1, N+1)}
for c in cands:
    dp[c[1]] = int(c[0])
for i in range(2, N+1):
    for c in cands:
        j = i - c[1]
        if j >= 1 and dp[j] is not None:
            if dp[i] is None:
                dp[i] = int(''.join(sorted(str(dp[j]) + c[0], reverse=True)))
            else:
                dp[i] = max(dp[i], int(''.join(sorted(str(dp[j]) + c[0], reverse=True))))
print(dp[N])

### FIXED CODE ###

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

numbers = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = {i: -1 for i in range(N+1)}
dp[0] = 0
for i in range(N+1):
    for a in A:
        j = i + numbers[a]
        if j <= N:
            dp[j] = max(dp[j], dp[i]*10 + a)
print(dp[N])
### BUGGY CODE ###

#DAGの最長有向パスをトポロジカルソートで解く
from collections import defaultdict

N,M=map(int,input().split(' '))
x=[0]*M
y=[0]*M
d=defaultdict(int)
for i in range(M):
    x[i],y[i]=map(int,input().split(' '))
n=set(i for i in range(1,N+1))
while len(n)>0:
    for i in n-set(y):
        n.remove(i)
        for j in range(M):
            if i==x[j]:
                if d[y[j]]<=d[i]:
                    d[y[j]]=d[i]+1
                y[j]=0
print(max(d.values()))

### FIXED CODE ###

from collections import defaultdict, deque

N, M = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(M)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1
length=defaultdict(int)

q = deque(set(i for i in range(1,N+1))-set(ins.keys()))
length=defaultdict(int)
while q:
    v1 = q.popleft()
    for v2 in outs[v1]:
        ins[v2] -= 1
        if length[v2]<=length[v1]:
            length[v2]=length[v1]+1
        if ins[v2] == 0:
            q.append(v2)

print(max(length.values()))
### BUGGY CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    rs = []
    for i in range(1, n + 1):
        r = 0
        for x in range(1, 100):
            for y in range(x, 100):
                for z in range(y, 100):
                    if f(x, y, z) > i:
                        break
                    elif f(x, y, z) == i:
                        if x == y == z:
                            r += 1
                        elif x == y or y == z or z == x:
                            r += 3
                        else:
                            r += 6
        rs.append(r)

    return rs


if __name__ == '__main__':
    main()


### FIXED CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    result = [0] * n
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                m = f(x, y, z)
                if m > n:
                    break
                result[m - 1] += 1

    return result


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

def main():
    h, w, k = map(int, raw_input().split())
    c = [map(int, raw_input().strip()) for _ in xrange(h)]
    def go(a):
        for j in xrange(w):
            st = [a[i][j] for i in xrange(h) if a[i][j]]
            for i in xrange(h):
                a[i][j] = 0
            i = -1
            for x in reversed(st):
                a[i][j] = x
                i -= 1
        res = 0
        for i in xrange(h):
            j = 0
            while j < w:
                t = j
                while t < w and a[i][j] == a[i][t]:
                    t += 1
                if t - j >= k:
                    for j in xrange(j, t):
                        res += a[i][j]
                        a[i][j] = 0
                j = t
        if not res:
            return 0
        return go(a) * 2 + res
    ans = 0
    for i in xrange(h):
        for j in xrange(w):
            t = [c[ii][:] for ii in xrange(h)]
            t[i][j] = 0
            r = go(t)
            if ans < r:
                ans = r
    print ans
main()


### FIXED CODE ###

def main():
    h, w, k = map(int, raw_input().split())
    c = [map(int, raw_input().strip()) for _ in xrange(h)]
    def go(a):
        if not res:
            return 0
        return go(a) * 2 + res
    ans = 0
    for ii in xrange(h):
        for jj in xrange(w):
            a = [c[i][:] for i in xrange(h)]
            a[ii][jj] = 0
            r = 0
            e = 1
            while 1:
                for j in xrange(w):
                    st = [a[i][j] for i in xrange(h) if a[i][j]]
                    for i in xrange(h):
                        a[i][j] = 0
                    i = -1
                    for x in reversed(st):
                        a[i][j] = x
                        i -= 1
                res = 0
                for i in xrange(h):
                    j = 0
                    while j < w:
                        t = j + 1
                        while t < w and a[i][j] == a[i][t]:
                            t += 1
                        if t - j >= k:
                            for j in xrange(j, t):
                                res += a[i][j]
                                a[i][j] = 0
                        j = t
                if not res:
                    break
                r += res * e
                e *= 2
            if ans < r:
                ans = r
    print ans
main()
### BUGGY CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

h,w = ma()
A = []
for i in range(h):
    A.append(lma())
B= []
for i in range(h):
    B.append(lma())
D = [[abs(A[i][j]-B[i][j]) for j in range(w)] for i in range(h)]
prev = [[False]*(2*80*w+1) for j in range(w)]
nex = [[False]*(2*80*w+1) for j in range(w)]
prev[0][0]=True
for i in range(h):
    for j in range(w):
        d = D[i][j]
        if j==0:
            for k in range(2*80*w+1-d):
                nex[j][k+d] = nex[j][k+d] or prev[j][k]
                nex[j][abs(k-d)] = nex[j][abs(k-d)] or prev[j][k]
        else:
            for k in range(2*80*w+1-d):
                nex[j][k+d] = nex[j][k+d] or prev[j][k] or nex[j-1][k]
                nex[j][abs(k-d)] = nex[j][abs(k-d)] or prev[j][k] or nex[j-1][k]
    prev=nex
    nex=[[False]*(2*80*w+1) for j in range(w)]
for i in range(2*80*w+1):
    if prev[w-1][i]:
        print(i)
        exit()


### FIXED CODE ###

ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

h,w = ma()
A = []
for i in range(h):
    A.append(lma())
B= []
for i in range(h):
    B.append(lma())
D = [[abs(A[i][j]-B[i][j]) for j in range(w)] for i in range(h)]
mx = 0
for i in range(h):
    for j in range(w):
        mx = max(mx,D[i][j])

le = (h+w)*mx
prev = [0]*w
nex = [0]*w
prev[0]=prev[0] | 2**le
for i in range(h):
    for j in range(w):
        d = D[i][j]
        if j==0:
            nex[j] = nex[j] | prev[j]>>d |prev[j]<<d
        else:
            nex[j] = nex[j] | prev[j]>>d |prev[j]<<d
            nex[j] = nex[j] | nex[j-1]>>d |nex[j-1]<<d
        #print(i,j,d,bin(nex[j]))
    prev=nex
    nex = [0]*w
for i in range(le+1):
    if (prev[w-1]>>le+i &1) or (prev[w-1]>>le-i &1):
        print(i)
        exit()
### BUGGY CODE ###

def main(N, A):
    ans = 0
    for i in range(N-1):
        ans += A[i]*sum(A[i+1:])
        ans %= 10**9 + 7
        """
        for j in range(i+1, N):
            ans += A[i]*A[j]
            ans = ans % (10**9 + 7)
        """
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)



### FIXED CODE ###

def main(N, A):
    ans = 0
    culm = sum(A)
    for i in range(N-1):
        culm -= A[i]
        ans += A[i]*culm
        ans %= 10**9 + 7
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)