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

#!python3

import sys
from collections import defaultdict
from math import gcd
from fractions import Fraction

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    inf = 10**18+1
    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for i, (ai, bi) in enumerate(zip(it, it)):
        if ai * bi  == 0:
            if ai != 0:
                ai = inf
                bi = 1
            elif bi != 0:
                ai = -1
                bi = inf
            else:
                z0 += 1
                continue
        val = Fraction(ai, bi)
        d1[0 if val >= 0 else 1][val] += 1

    a1, a2 = d1
    ans = 1
    for k, v in a1.items():
        ik = -1/k
        if ik in a2:
            v2 = a2[ik]
            ans *= pow(2, v+v2, mod) - (pow(2, v, mod)-1)*(pow(2, v2, mod)-1)
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for k, v in a2.items():
        ik = -1/k
        if not ik in a1:
            ans *= pow(2, v, mod)
            ans %= mod

    print(ans-1+z0)



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
from collections import defaultdict
from math import gcd

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai * bi < 0
        if ai < 0:
            ai, bi = -ai ,-bi
        elif ai == 0:
            bi = -1
            t = 1

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v, mod) + pow(2, v2, mod) - 1
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        ans *= pow(2, v, mod)
        ans %= mod

    print((ans-1+z0) % mod)



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

H,W=map(int,input().split())
Grid=[]
for _ in range(H):
  Grid.append(list(input()))
tmp=0
ans=0
up=[[0 for _ in range(W)] for _ in range(H)]
down=[[0 for _ in range(W)] for _ in range(H)]
left=[[0 for _ in range(W)] for _ in range(H)]
right=[[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if Grid[i][j]=='.':
      left[i][j]=left[i][j-1]+1
      up[i][j]=up[i-1][j]+1
    if Grid[H-i-1][j]=='.':
      down[H-i-1][j]=down[-i][j]+1
    if Grid[i][W-j-1]=='.':
      right[i][W-j-1]=right[i][-j]+1
      
for i in range(H):
  for j in range(W):
    ans=max(ans,left[i][j]+up[i][j]+down[i][j]+right[i][j]-3)
print(ans)    

### FIXED CODE ###

H,W=map(int,input().split())
Grid=[]
for _ in range(H):
  Grid.append(list(input()))
tmp=0
ans=0
up=[[0 for _ in range(W)] for _ in range(H)]
down=[[0 for _ in range(W)] for _ in range(H)]
left=[[0 for _ in range(W)] for _ in range(H)]
right=[[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if Grid[i][j]=='.':
      left[i][j]=left[i][j-1]+1
      up[i][j]=up[i-1][j]+1
    if Grid[H-i-1][j]=='.':
      down[H-i-1][j]=down[-i][j]+1
    if Grid[i][W-j-1]=='.':
      right[i][W-j-1]=right[i][-j]+1
      
for i in range(H):
  for j in range(W):
    ans=max(ans,left[i][j]+up[i][j]+down[i][j]+right[i][j]-3)
print(ans)
### BUGGY CODE ###

# coding: utf-8

line = input()
data = line.split(" ")
shoplist = [] #店のデータリスト
for i in range(int(data[0])):
    shop = input()
    shopdata = shop.split(" ")
    shop_int = []
    for j in range(len(shopdata)):
        shop_int.append(int(shopdata[j]))
    shoplist.append(shop_int)

payment = 0 #支払い金額
wantdrink = int(data[1]) #ほしい飲み物の数
pricelist = []  #金額のみのデータリスト
for i in range(len(shoplist)):
    pricelist.append(shoplist[i][0])
while wantdrink > 0 :
    pricemin = min(pricelist[i] for i in range(len(pricelist)))
    min_index = pricelist.index(pricemin)
    restdrink = shoplist[min_index][1]
    if restdrink >= wantdrink:
      while restdrink > 0:
        payment += pricemin
        restdrink -= 1
        wantdrink -= 1
        if wantdrink == 0:
              break
    else:
        payment += restdrink * pricemin
        wantdrink -= restdrink
    del shoplist[min_index]
    del pricelist[min_index]
print(payment)

### FIXED CODE ###

# coding: utf-8

data = input().split()
shoplist = []
for i in range(int(data[0])):
    shopdata = list(map(int, input().split()))
    shoplist.append(shopdata)
shoplist.sort()

payment = 0
wantdrink = int(data[1])
while wantdrink > 0 :
    restdrink = shoplist[0][1]
    if restdrink >= wantdrink:
        payment += wantdrink * shoplist[0][0]
        break
    else:
        payment += restdrink * shoplist[0][0]
        wantdrink -= restdrink
        del shoplist[0]
print(payment)
### BUGGY CODE ###

n = int(input())

p = 1

for i in range(1, n+1):
    p *= i
print(p%(10**9+7))

### FIXED CODE ###

n = int(input())

p = 1

for i in range(1, n+1):
    p = p*i%(10**9+7)
print(p)
### BUGGY CODE ###

n, m = [int(v) for v in input().split(' ')]

costs = []
links = []
for i in range(n):
    costs.append([0] * i)
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]

    for j in range(l, r):
        j1 = j - 1
        for k in range(j + 1, r + 1):
            k1 = k - 1
            c0 = costs[k1][j1]
            if c0 == 0 or c0 > c:
                costs[k1][j1] = c

                links[k1].append(j1)
                links[j1].append(k1)

import heapq
h = []
closed = 0

heapq.heappush(h, (0, n-1))

while len(h) > 0:
    c0, n1 = heapq.heappop(h)
    closed |= (1 << n1)

    if n1 == 0:
        print(c0)
        exit()

    for i in links[n1]:
        if closed & (1 << i) != 0:
            continue

        c1 = 0
        if i < n1:
            c1 = costs[n1][i]
        elif i > n1:
            c1 = costs[i][n1]
        if c1 > 0:
            heapq.heappush(h, (c0 + c1, i))

print("-1")

### FIXED CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if (closed & (1 << n0)) != 0:
        continue
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n2))

print("-1")
### BUGGY CODE ###

MOD = 10 ** 9 + 7
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    t = 0
    for i, Ai in enumerate(A[:-1]):
        t = (t + sum(Ai ^ Aj for Aj in A[i + 1:])) % MOD
    print(t)

main()


### FIXED CODE ###

MOD = 10 ** 9 + 7
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0] * 60
    for i in A:
        for j in range(60):
            if i & (1 << j):
                B[j] += 1
    r = 0
    for ii, i in enumerate(A[:-1]):
        for j in range(60):
            if i & (1 << j):
                B[j] -= 1
                r = (r + (1 << j) * (N - ii - 1 - B[j])) % MOD
            else:
                r = (r + (1 << j) * B[j]) % MOD
    print(r)

main()
### BUGGY CODE ###

n = int(input())

an = map(int, input().split())

num = 1
for i in an:
    num *= i
    
if num > 10**18:
    print(-1)
else:
    print(num)    

### FIXED CODE ###

n = int(input())
an = map(int, input().split())
num = 1
max = 10**18
for i in an:
    if num < max:
         num *= i
    if (i == 0):
        num = 0
        break
    
if num > 10**18:
    print(-1)
else:
    print(num)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

arr1 = {}
for i,x in enumerate(A):
	arr1[i+1] = x

arr2 = sorted(arr1.items(), key=lambda x:x[1])

ans = ''
for k,v in arr2:
	if v == 1:
		ans = str(k)
	else:
		ans = ans + ' ' + str(k)

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

arr1 = {}
for i,x in enumerate(A):
	arr1[i+1] = x

arr2 = sorted(arr1.items(), key=lambda x:x[1])

ans = ''
for k,v in arr2:
		print(k)
### BUGGY CODE ###

import sys
import math
input = sys.stdin.readline

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

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

ans=[0]*N

ans[N-2]=abs(arr[-2]-arr[-1])

for i in range(N-3,-1,-1):
	minn=100000000000000
	for j in range(min(K,N-i-1)):
		minn = min(minn,abs(arr[i]-arr[i+j+1])+ans[i+j+1])
	ans[i]=minn

print(ans[0])

### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

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

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

ans=[0]*N

ans[N-2]=abs(arr[-2]-arr[-1])

for i in range(N-3,-1,-1):
	minn=100000000000000
	for j in range(min(K,N-i-1)):
		minn = min(minn,abs(arr[i]-arr[i+j+1])+ans[i+j+1])
	ans[i]=minn

print(ans[0])
### BUGGY CODE ###

n = int(input())
arr = {}

for i in range(n):
    s = input()
    if not s in arr:
        arr[s] = 1
    else:
        arr[s] += 1

dic = [key[0] for key in arr.items() if key[1] == max(arr.values())]
for i in sorted(dic):
    print(i)

### FIXED CODE ###

n = int(input())
arr = {}

for i in range(n):
    s = input()
    if not s in arr:
        arr[s] = 1
    else:
        arr[s] += 1

max_count = max(arr.values())
dic = [key[0] for key in arr.items() if key[1] == max_count]

out_sort = sorted(dic)
for i in out_sort:
    print(i)
### BUGGY CODE ###

import sys

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = set([1])
n = gcd+1
for i in range(2, n):
    while True:
        if gcd%i ==0:
            L.add(i)
            gcd = gcd//i
        else:
            break
    if gcd < i:
        break
L = set(L)
print(len(L))

### FIXED CODE ###

import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect_left
from bisect import bisect

N, Q = map(int,input().split())
C = list(map(int,input().split()))

d = defaultdict(list)

for i,c in enumerate(C):
    d[c]+=[i]

for _ in range(Q):
    l, r = map(int,input().split())
    print(sum(bisect(L, r-1)-bisect_left(L, l-1) > 0 for L in d.values()))

### FIXED CODE ###

import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()
### BUGGY CODE ###

import sys
import bisect

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def bis_insert(L, target, top=None, bottom=None):
    if top is None:
        top = len(L)
    if bottom is None:
        bottom = 0

    while bottom < top:
        half = (top + bottom) // 2
        if target > L[half]:
            bottom = half + 1
        else:
            top = half
    return bottom


def solve(inputs):
    L = string_to_int(inputs[0])
    L.sort()
    total_count = 0
    for i in range(len(L) - 2):
        for j in range(i + 1, len(L)-1):
            a = L[i]
            b = L[j]
            target = a + b
            r = bis_insert(L, target)
            total_count += r - j - 1
    return total_count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)

### FIXED CODE ###

import sys
import bisect

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def bis_insert(L, target, top=None, bottom=None):
    if top is None:
        top = len(L)
    if bottom is None:
        bottom = 0

    while bottom < top:
        half = (top + bottom) // 2
        if target > L[half]:
            bottom = half + 1
        else:
            top = half
    return bottom


def solve(inputs):
    L = string_to_int(inputs[0])
    L.sort()
    total_count = 0
    for i in range(len(L) - 2):
        for j in range(i + 1, len(L)-1):
            a = L[i]
            b = L[j]
            target = a + b
            # r = bis_insert(L, target)
            r = bisect.bisect_left(L, target)
            total_count += r - j - 1
    return total_count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
t = [0] * n
x = [0] * n
y = [0] * n
for i in range(n):
    t[i],x[i],y[i] = map(int,input().split())

def travel(x,y,t):
    if t == t_st:
        if x == x_st and y == y_st:
            return True
        else:
            return False
    if travel(x-1,y,t-1) or travel(x,y-1,t-1) or travel(x+1,y,t-1) or travel(x,y+1,t-1):
        return True
    else:
        return False

t_st = 0
x_st = 0
y_st = 0

ans = travel(x[0],y[0],t[0])

for i in range(1,n):
    x_st = x[i-1]
    y_st = y[i-1]
    t_st = t[i-1]
    if travel(x[i],y[i],t[i]):
        pass
    else:
        ans = False

if ans:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
t = [0] * n
x = [0] * n
y = [0] * n
for i in range(n):
    t[i],x[i],y[i] = map(int,input().split())

def travel(x,y,t):
    if abs(t-t_st) >= abs(x-x_st) + abs(y-y_st) and abs(t-t_st) % 2 == (abs(x-x_st) + abs(y-y_st)) % 2:
        return True
    else:
        return False

t_st = 0
x_st = 0
y_st = 0

ans = travel(x[0],y[0],t[0])

for i in range(1,n):
    x_st = x[i-1]
    y_st = y[i-1]
    t_st = t[i-1]
    if travel(x[i],y[i],t[i]):
        pass
    else:
        ans = False

if ans:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

s = input()
q = int(input())

isRev = False

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        isRev = not isRev
    else:
        if isRev:
            s = ''.join(list(reversed(s)))
        if query[1] == '1':
            s = query[2] + s
        elif query[1] == '2':
            s = s + query[2]
        isRev = False
            
if isRev:
    s = ''.join(list(reversed(s)))
        
print(s)
        

### FIXED CODE ###

from sys import stdin
input = stdin.readline

s = input().rstrip()
q = int(input())

isRev = False

head = ''

for i in range(q):
    query = list(input().split())
    if len(query) == 1:
        isRev = not isRev
    else:
        if isRev and query[1] == '1':
            s = s + query[2]
        elif query[1] == '1':
            head = head + query[2]
        elif isRev and query[1] == '2':
            head = head + query[2]
        elif query[1] == '2':
            s = s + query[2]
            
if isRev:
    s = s[::-1] + head
else:
    s = head[::-1] + s
        
print(s)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read

n,*x = list(map(int, read().split()))


for i in range(0,n):
  temp = []
  try:
    temp = x[:i]
  except:
    pass
  try:
    temp += x[i+1:]
  except:
    pass
  temp.sort()
  print(temp[n//2-1])

### FIXED CODE ###

import sys

read = sys.stdin.buffer.read

n,*x = list(map(int, read().split()))
x_sort = sorted(x)

mean_left = x_sort[n//2-1]
mean_right = x_sort[n//2]


for i in range(n):
  if x[i] <= mean_left:
    print(mean_right)
  elif x[i] >= mean_right:
    print(mean_left)
### BUGGY CODE ###

n=int(input())
orislis=[]
oricount=[]
for i in range(n):
	s=sorted(list(input()))
	if s not in orislis:
		orislis.append(s)
		oricount.append(1)
	else:
		oricount[orislis.index(s)]+=1
ans=0
for i in oricount:
	z=(i*(i-1))/2
	ans+=z
print(int(ans))

### FIXED CODE ###

from collections import Counter
n=int(input())
slis=[]
for i in range(n):
	s=sorted(list(input()))
	slis.append(s)
ctr=Counter()
ans=0
for s in slis:
	a="".join(s)
	if a in ctr:
		ans+=ctr[a]
	ctr[a] +=1
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    """
    if n % r == 0:
        ans += 1
        continue
    """
    if n - r*i < 0:
        continue
    for j in range((n-r*i)//g+1):
        """
        if n % g == 0:
            ans += 1
            continue
        """
        if n - r*i - g*j < 0:
            continue
        if (n - r*i - g*j)%b == 0:
            ans += 1

        # print(n,i,j,n - i*r - j*g,ans)
print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range((n-r*i)//g+1):
        if (n - r*i - g*j)%b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

from sys import stdin
from functools import reduce


def comb_mod(n, a, mod=10**9+7):
    # https://img.atcoder.jp/abc156/editorial.pdf
    # nCk は, k回の積で計算できる
    num = reduce(lambda x, y: x * y % mod, range(n, n - a, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, a + 1))
    # nCk mod = X/Y mod = X * Y^(10**9+7-2) mod
    return num * pow(den, mod - 2, mod) % mod


# not AC
def get_result(data):
    n, a, b = data[0]
    mod = 10**9+7
    out = (2 ** n) % mod - comb_mod(n, a, mod) - comb_mod(n, b, mod) - 1 
    out %= mod
    return out

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin
from functools import reduce


def comb_mod(n, a, mod=10**9+7):
    # https://img.atcoder.jp/abc156/editorial.pdf
    # nCk は, k回の積で計算できる
    num = reduce(lambda x, y: x * y % mod, range(n, n - a, -1))
    den = reduce(lambda x, y: x * y % mod, range(1, a + 1))
    # nCk mod = X/Y mod = X * Y^(10**9+7-2) mod
    return num * pow(den, mod - 2, mod) % mod


def get_result(data):
    n, a, b = data[0]
    mod = 10**9+7
    out = pow(2, n, mod) - comb_mod(n, a, mod) - comb_mod(n, b, mod) - 1 
    out %= mod
    return out

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

# coding: utf-8
import itertools
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
d = 0
maxd = 0
for m in range(1, n + 1):
    a0 = [list(i) for i in list(itertools.combinations(list(range(n)), m))]
    for a1 in a0:
        x = sum([v[j] for j in a1])
        y = sum([c[j] for j in a1])
        d = x - y
        if maxd < d:
            maxd = d
print(maxd)


### FIXED CODE ###

# coding: utf-8
import itertools
n = int(input())
v = list(map(int, input().split()))
c = list(map(int, input().split()))
d = sum([v[i] - c[i] for i in range(n) if v[i] - c[i] > 0])
print(d)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))

H,W=MI()
A,B=[],[]
for _ in [0]*H:
    A.append(LI())
    
for _ in [0]*H:
    B.append(LI())
    
G=[[set() for i in range(W)] for j in range(H)]
dif=A[0][0]-B[0][0]
G[0][0].add(0)

M=-1
for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        M=max(M,abs(d))

M*=(H+W)
res=[[[False]*(2*M+1) for _ in [0]*W] for _ in [0]*H]

for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        for a in G[h][w]:
            if h!=H-1:
                G[h+1][w].add(a+d)
                G[h+1][w].add(a-d)
            if w!=W-1:
                G[h][w+1].add(a+d)
                G[h][w+1].add(a-d)
    
res=set()
for a in G[H-1][W-1]:
    res.add(a)
d=A[H-1][W-1]-B[H-1][W-1]
for a in G[H-1][W-1]:
    res.add(a+d)
    res.add(a-d)

res=list(res)
res1=sorted([-r for r in res if r<=0])
res2=sorted([r for r in res if r>=0])
print(min(res1[0],res2[0]))

# for h in range(H):
#     for w in range(W):
#         print(list(G[h][w]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))

H,W=MI()
A=[LI() for _ in [0]*H]
B=[LI() for _ in [0]*H]

G=[[set() for i in range(W)] for j in range(H)]
G[0][0].add(0)

for h in range(H):
    for w in range(W):
        d=A[h][w]-B[h][w]
        for a in G[h][w]:
            if h!=H-1:
                G[h+1][w].add(abs(a+d))
                G[h+1][w].add(abs(a-d))
            if w!=W-1:
                G[h][w+1].add(abs(a+d))
                G[h][w+1].add(abs(a-d))

res=set()
d=A[H-1][W-1]-B[H-1][W-1]
for a in G[H-1][W-1]:
    res.add(abs(a+d))
    res.add(abs(a-d))

res=sorted(list(res))
print(min(res))
### BUGGY CODE ###

def main():
    _ = input()
    lst_a = [int(a) for a in input().strip().split(' ')]

    # build hash table
    hash_tbl = {}
    for i, a_i in enumerate(lst_a):
        n_i = i + 1
        tmp = int(n_i - a_i)
        if tmp > 0:
            if tmp in hash_tbl.keys():
                hash_tbl[tmp].append(n_i)
            else:
                hash_tbl[tmp] = [n_i]

    ans = 0
    for j, a_j in enumerate(lst_a):
        n_j = j + 1
        tmp = int(n_j + a_j)
        if tmp in hash_tbl.keys():
            ans += len([idx for idx in hash_tbl[tmp] if idx > j])
    print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    _ = input()
    lst_a = [int(a) for a in input().strip().split(' ')]

    # build hash table
    hash_tbl = {}
    for i, a_i in enumerate(lst_a):
        n_i = i + 1
        tmp = int(n_i - a_i)
        if tmp > 0:
            if tmp in hash_tbl.keys():
                hash_tbl[tmp].append(n_i)
            else:
                hash_tbl[tmp] = [n_i]

    ans = 0
    for j, a_j in enumerate(lst_a):
        n_j = j + 1
        tmp = int(n_j + a_j)
        if tmp in hash_tbl.keys():
            # ans += len([idx for idx in hash_tbl[tmp] if idx > j])
            ans += len(hash_tbl[tmp])
    print(int(ans))


if __name__ == '__main__':
    main()