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

N = int(input())
B = input()
B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)


for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - ((2**(N-i-1)) % (B_1-1))) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + ((2**(N-i-1)) % (B_1+1))) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))

### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
### BUGGY CODE ###

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

def check(l):
    for i in range(N - 2 * l + 1):
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

### FIXED CODE ###

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

dp = [[0 for _ in range(N)] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
a = [int(i) for i in input().split()]

p = list(itertools.permutations(a,len(a)))
y = 0
for l in p:
	c = 0
	for i in range(len(l)-1):
		if l[i] != int(bin(l[i-1]^l[i+1]),0):
			c=1
			break
	if c==0:
		if l[-1] == int(bin(l[0]^l[-2]),0):
			y=1
			break
			
if y==1:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
sum = 0
for i in a:
	sum^=i
if sum == 0:
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1);graph[b-1].append(a-1)

mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

size = [1] * (n+1)
dp = [1] * (n+1)    
for child in orders[::-1]:
    parent = parents[child]
    size[parent] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
_ = size.pop();_ = dp.pop()

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp2[child] * ifac[size2[child]-1] * dp[child] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) * fac[size[parent]] % mod

for i in range(n):
    print(fac[n-1]*dp[i]*ifac[size[i]-1]*dp2[i]*ifac[size2[i]-1] % mod)

### FIXED CODE ###

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n-1)]
mod = 10**9+7

graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

parents = [-1] * n
children = [[] for _ in range(n)]
flags = [True] * n; flags[0] = False
stack = [0]
orders = []

while stack:
    index = stack.pop()
    orders.append(index)
    for child in graph[index]:
        if flags[child]:
            parents[child] = index
            children[index].append(child)
            flags[child] = False
            stack.append(child)

fac = [1] * (n+10)
inv = [1] * (n+10)
ifac = [1] * (n+10)
for i in range(2,n+10):
    fac[i]=(fac[i-1]*i)%mod
    inv[i]= -(inv[mod%i]*(mod//i))%mod
    ifac[i]=(ifac[i-1]*inv[i])%mod

size = [1] * n
dp = [1] * n
for parent in orders[::-1]:
    for child in children[parent]:
        size[parent] += size[child]
        dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
    dp[parent] = dp[parent] * fac[size[parent]-1] % mod

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp[child] * dp2[child] * fac[size[parent]] * ifac[size2[child]-1] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) % mod
    
for i in range(n):
    print(fac[n-1] * ifac[size[i]-1] * ifac[size2[i]-1] * dp[i] * dp2[i] % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
s = input().rstrip()

def split(s):
    new = [s[0]]
    for i in range(n-1):
        if s[i] != s[i+1]:
            new.append(s[i+1])
        else:
            new[-1] += s[i+1]
    return new

def transform(s, k):
    for _ in range(k):
        s = split(s)
        if len(s) == 1:
            s = ''.join(s)
            break
        idx = 1
        s[idx] = s[idx].replace('L', 'X').replace('R', 'L').replace('X', 'R')
        s = ''.join(s)
    return s


s = transform(s, k)


def count(s):
    cnt = 0
    for i in range(n):
        if i+1 < len(s) and s[i] == 'R' and s[i+1] == 'R':
            cnt += 1
        elif i-1 >= 0 and s[i] == 'L' and s[i-1] == 'L':
            cnt += 1
    return cnt


print(count(s))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, k = map(int, input().split())
s = input().rstrip()

def count(s):
    cnt = 0
    for i in range(n):
        if i+1 < len(s) and s[i] == 'R' and s[i+1] == 'R':
            cnt += 1
        elif i-1 >= 0 and s[i] == 'L' and s[i-1] == 'L':
            cnt += 1
    return cnt


print(min(count(s)+2*k, n-1))
### BUGGY CODE ###

import collections
N = int(input())
c = collections.Counter([input() for _ in range(N)])
[print(sorted([k for k, v in c.items() if  v == max(c.values())])[i]) \
 for i in range(len([k for k, v in c.items() if  v == max(c.values())]))]

### FIXED CODE ###

import collections
N = int(input())
S = [input() for _ in range(N)]

if len(S) == len(set(S)):
  ans = S
else:
  ans = []
  c = collections.Counter(S)
  c_common = c.most_common()
  max_vote = c_common[0][1]
  for k in range(len(set(S))):
    if c_common[k][1]== max_vote:
      ans.append(c_common[k][0])
    else:
      break
[print(a) for a in sorted(ans)]
### BUGGY CODE ###

N = int(input())
s = [list(input()) for _ in range(N)]
l = []
cnt = 0
for st in s:
    st.sort()
    l.append("".join(st))
l.sort()
a = list(set(l))
for uni in a:
    c = l.count(uni)
    if c>1:
        cnt += (1+(c-1))*(c-1)//2
print(cnt)

### FIXED CODE ###

N = int(input())
s = [list(input()) for _ in range(N)]
l = []
for st in s:
    st.sort()
    l.append("".join(st))
l.sort()
cnt = 0
c = 1
for i in range(N-1):
    if l[i]==l[i+1]:
        c += 1
    else:
        if c>1:
            cnt += (1+(c-1))*(c-1)//2
        c = 1
print(cnt+(1+(c-1))*(c-1)//2)
### BUGGY CODE ###

N = int(input())

sList = []
ans = 0

#文字を読み込みつつ、出現回数を辞書化して、配列に追加
for i in range(N):
    # https://www.lifewithpython.com/2015/05/python-count-characters-in-string.html
    string = str(input())
    counter = {}
    
    #辞書化
    for c in string:
        if not c in counter:
            counter[c] = 1
        else:
            counter[c] += 1
            
    sList.append(counter)
    
#全通りを比較
for i in range(N-1):
    for j in range(i+1,N,1):
        if sList[i]==sList[j]:
            ans = ans+1
            
print(ans)

### FIXED CODE ###

#137c
N = int(input())
s_dict = {}
ans = 0

#文字を読み込みつつ、出現回数を辞書化して、辞書に追加
for i in range(N): #2<N<10^5
  # https://www.lifewithpython.com/2015/05/python-count-characters-in-string.html
  string = list(input())
  string.sort(reverse=False)
  
  #print(tuple(string))
    
  if tuple(string) in s_dict:
    s_dict[tuple(string)] += 1
  else:
    s_dict[tuple(string)] = 1

for i in s_dict.values():
  if i != 1:
    ans += sum([i for i in range(1,i)])

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

n,m = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
add = []
for _ in range(m):
    b,c = map(int,input().split())
    add += [c]*b
add.sort(reverse=True)
ans = 0
#print(len(li),len(add))
if len(li)>len(add):
    ans = sum(li[len(add):])
#print(fin)
for l,a in zip(li,add):
    #print(l,a)
    if a>l:
        ans += a
    else:
        ans += l
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
li = list(map(int,input().split()))
tmp_li = []
for _ in range(m):
    b,c = map(int,input().split())
    tmp_li.append((c,b))
tmp_li.sort(reverse=True)
#print(tmp_li)
for c,b in tmp_li:
    li.extend([c]*b)
    if len(li)>= 2*n:
        break
li.sort(reverse=True)
print(sum(li[:n]))
### BUGGY CODE ###

K = input()

#ユーグリッド互除法（再起）
def gcd(p, q):
  # ユーグリッド互除法
  if (p%q==0):
    return q
  else:
    return gcd(q, p%q)

ans = 0

#すべての組合せ(n^3)
abc_list = []
for a in range(1, int(K)+1):
  for b in range(1, int(K)+1):
    for c in range(1, int(K)+1):
        gcd_ab = gcd(a, b)
        gcd_abc = gcd(gcd_ab, c)
        ans += gcd_abc

print(ans)

### FIXED CODE ###

import itertools
K = int(input())

#ユーグリッド互除法（再起）
def gcd(p, q):
  # ユーグリッド互除法
  if (p%q==0):
    return q
  else:
    return gcd(q, p%q)

ans = 0

for abc in itertools.combinations_with_replacement([i+1 for i in range(K)], 3):
  a,b,c = abc
  gcd_ab = gcd(a, b)
  gcd_abc = gcd(gcd_ab, c)

  # 組み合わせ数を補整する
  if a == b == c:
    ans += gcd_abc
  elif a==b or b==c or a==c:
    ans += gcd_abc*3
  else:
    ans += gcd_abc * 6

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

s = str(input())

num_moto = int(len(s))

for ctr in range(5000):
    if int(len(s)) == 0:
        break
    s = s.replace('10','')
    s = s.replace('01','')
    
num_kekka = int(len(s))
print(num_moto - num_kekka)

### FIXED CODE ###

s = input()
count_0 = s.count('0')
count_1 = s.count('1')
print(2*min(count_0,count_1))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N = int(input())
import collections

As = [collections.deque()]
for i in range(N):
    As.append(collections.deque(map(int, input().split())))

Ks = [False] * (N + 1)
d = 1
ms = 0
msMax = N * (N - 1) // 2
sw = True
tab = set()
wa = [0] * (N + 1)
while sw:
    wac = 0
    c = 0
    e = N + 1
    f = N - 1
    for i in range(1, e):
        if Ks[i] or len(As[i]) == 0:
            continue
        p = As[i].popleft()
        if i > p:
            a = p
            b = i
        else:
            a = i
            b = p
        if (a, b) in tab:
            ms = ms + 1
            c = c + 1
            if ms == msMax:
                sw = False
                print(d)
                break
            tab.remove((a, b))
            Ks[a] = False
            wa[wac] = b
            wac = wac + 1
        else:
            tab.add((a, b))
            Ks[i] = True
    for i in range(N):
        if wa[i] == 0:
            break
        Ks[wa[i]] = False
        wa[i] = 0
    d = d + 1
    if c == 0:
        print(-1)
        break

### FIXED CODE ###

import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

n = int(input())
b = list(map(str, input().split()))
''.join(b)
ans = []
def dfs(b):
    if len(b) == 1:
        if int(b[0]) == 1:
            return True
    else:
        for i in range(len(b)):
            if int(b[i]) == i + 1:
                if i == 0:
                    if dfs(b[1:]):
                        ans.append(i + 1)
                        return True
                else:
                    if dfs(b[:i] + b[i+1:]):
                        ans.append(i + 1)
                        return True
        return False
if dfs(b):
    ans.insert(0, 1)
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
while(len(b) != 1):
    count = 0
    for i in range(len(b) - 1, -1, -1):
        if b[i] == i + 1:
            b.pop(i)
            ans.append(i + 1)
            count = 0
            break
        else:
            count += 1
    if count == len(b):
        print(-1)
        exit()
if b[0] == 1:
    ans.append(1)
    ans = list(reversed(ans))
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,u):
    rt=0
    q=deque([(t,s,u)])
    while q:
        y,x,depth=q.popleft()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx,depth+1))
    return -1

dis=bfs(0,0,1)
ans=wh-dis if dis>=0 else dis
print(ans)


### FIXED CODE ###

from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s):
    rt=0
    q=deque([(t,s)])
    v[t][s]=1
    while q:
        y,x=q.popleft()
        if (y,x)==(h-1,w-1):  # condtion for finish
            return
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx))
                    v[y+dy][x+dx]=v[y][x]+1
    return -1

bfs(0,0)
dis=v[-1][-1]
ans=wh-dis if dis>0 else -1
print(ans)
### BUGGY CODE ###

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

sumA, sumB = [0], [0]
sa, sb = 0, 0
for a in A:
    sa += a
    sumA.append(sa)
for b in B:
    sb += b
    sumB.append(sb)

n_max = 0
for na in range(N+1):
    for nb in range(M+1):
        k = sumA[na] + sumB[nb]
        if k > K:
            break
        n = na + nb
        n_max = max(n_max, n)
print(n_max)


### FIXED CODE ###

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

sumA, sumB = [0], [0]
sa, sb = 0, 0
for a in A:
    sa += a
    sumA.append(sa)
for b in B:
    sb += b
    sumB.append(sb)


n_max = 0
nb_max = M
for na in range(0, N+1):
    for nb in range(nb_max, -1, -1):
        k = sumA[na] + sumB[nb]
        if k <= K:
            n = na + nb
            n_max = max(n_max, n)
            nb_max = nb
            break
print(n_max)
### BUGGY CODE ###

from collections import deque
n = int(input())
listx = [int(input()) for i in range(n)]
listx.sort()
listx = deque(listx)
listy = deque([])
ans=0

x=listx.popleft()
listy.appendleft(x)
x=listx.pop()
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while n-2 >=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop()
        listy.appendleft(x)
        ans+=abs2

    else:
        x=listx.popleft()
        listy.append(x)
        ans+=abs1
        
    if listy[0] > listy[-1]:
        listy.reverse()

    n += -1
        
print(ans)


### FIXED CODE ###

import itertools
import numpy as np
data_num = int(input()) 
data = [int(input()) for i in range(data_num)] 
#data_num=5
#data=[6,8,1,2,3]

data.sort()
npdata=np.array(data)

parts1=[1]
parts2=[2 for i in range(data_num-2)]
parts1.extend(parts2)
parts1.append(1)
npparts1=np.array(parts1)

parts0=[(-1)**(i+1) for i in range(data_num)]
npparts0=np.array(parts0)

y=npparts1*npparts0

y=y.tolist()
y.sort()

y=np.array(y)
z1=sum(data*y)

parts01=[(-1)**i for i in range(data_num)]
npparts0=np.array(parts01)

y=npparts1*npparts0

y=y.tolist()
y.sort()
y=np.array(y)
z2=sum(data*y)

print(max(z1,z2))
### BUGGY CODE ###

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

if max(A) < K:
    print('IMPOSSIBLE')
    exit()

if K in A:
    print('POSSIBLE')
    exit()

for i in range(len(A)):
    for j in range(i+1, len(A)):
        if i != j:
            A.append(abs(A[i] - A[j]))

set_A = list(set(A))

for i in range(len(set_A)):
    for j in range(i+1, len(set_A)):
        if abs(set_A[i] - set_A[j]) == K:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

### FIXED CODE ###

import fractions
from functools import reduce

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

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

G = gcd(*A)
M = max(A)

if K % G == 0 and M >= K:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import sys,math,copy
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    n = i % 2
    if s == -1:
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]

    else:
        m = (s * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]
    dp[n-1] = [0] * 13
    mod = (mod * 10) % 13
print(dp[N%2][5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[0 for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = 1
dp[0][0][0 + grid[0][0]] = 1
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i+1][j][k - grid[i+1][j]] = 1
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                else:
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i][j+1][k + grid[i][j+1]] = 1
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)