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

N, M = map(int, input().split())
PY = [list(map(int,input().split())) for i in range(M)]

ken_d = {k:[]  for k in range(1, N+1)}

for p in PY:
    ken_d[p[0]].append(p[1])

for k in ken_d.keys():
    ken_d[k].sort()

for p in PY:
    x = ken_d[p[0]].index(p[1]) + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
import sys
PY = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(M)]

# ken = {p[0] for p in PY}
# ken_d = {k:[] for k in ken}
ken_d = [[] for _ in range(N+1)]

rankdic = {} # 通し番号：県における順位

for i, p in enumerate(PY):
    # print(p)
    ken_d[p[0]].append([i, p[1]])

for k in range(N+1):
    ken_d[k].sort(key=lambda x:x[1])
    for i, v in enumerate(ken_d[k]):
        rankdic[v[0]] = i # 通し番号辞書に入れる

for i, p in enumerate(PY):
    x = rankdic[i] + 1
    print(str(p[0]).zfill(6) + str(x).zfill(6))
### BUGGY CODE ###

import heapq 
import math

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

lst = []
for i in range(n):
  lst.append([-a[i], 1])
  
heapq.heapify(lst)

for i in range(k):
  pop = heapq.heappop(lst)
  pop = [pop[0]*(pop[1])/(pop[1]+1), pop[1]+1]
  heapq.heappush(lst, pop)
  
pop = heapq.heappop(lst)
print(math.ceil(-pop[0]))

### FIXED CODE ###

n, k = map(int, input().split())
log = list(map(int, input().split()))

left = 0
right = 10**9

while right - left > 1:
  
  mid = (left + right) // 2
  
  cut = 0
  for i in range(n):
    cut += -(log[i]//-mid)-1

  if cut > k:
    left = mid
  else:
    right = mid
    
print(right)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
for i in range(N):
    tmp = [0]
    tmp.extend(L[:i])
    tmp.extend(L[i+1:])
    tmp.append(0)
    ans = 0
    for j, n in enumerate(tmp):
        if j == 0:
            pre = n
            continue
        ans += abs(pre - n)
        pre = n
    print(ans)

### FIXED CODE ###

A = [0]
N = int(input())
A.extend(list(map(int, input().split())))
A.append(0)
ALL = 0
for i in range(1, N+2):
    ALL += abs(A[i-1] - A[i])
for i in range(1, N+1):
    print(ALL - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1]))
### BUGGY CODE ###

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

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[float('inf')] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    # 経路情報は隣接行列に保持する(無向グラフなので両方向)
    G[a-1][b-1] = c
    G[b-1][a-1] = c

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 始点 = 終点、は例外的に距離0にしておく
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = float('inf')
# 町の順番は順列全部試す(最大8なら大丈夫)
for p in permutations(r):
    sm = 0
    # 最短経路を足し合わせていく
    for i in range(1, len(p)):
        sm += G[p[i-1]-1][p[i]-1]
    ans = min(sm, ans)
print(ans)


### FIXED CODE ###

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

from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
G = [[float('inf')] * (N) for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    # 経路情報は隣接行列に保持する(無向グラフなので両方向)
    G[a-1][b-1] = c
    G[b-1][a-1] = c

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 始点 = 終点、は例外的に距離0にしておく
            if i == j:
                G[i][j] = 0
            else:
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

ans = float('inf')
# 町の順番は順列全部試す(最大8なら大丈夫)
for p in permutations(r):
    sm = 0
    # 最短経路を足し合わせていく
    for i in range(1, len(p)):
        sm += G[p[i-1]-1][p[i]-1]
    ans = min(sm, ans)
print(ans)
### BUGGY CODE ###

def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7
    n = int(input())
    a = tuple(map(int, input().split()))

    b = [[0] * 60 for _ in range(n + 1)]

    for j in range(60):
        for i, x in enumerate(a, 1):
            if (x >> j) & 1:
                b[i][j] += 1

    for j in range(60):
        for i in range(1, n + 1):
            b[i][j] += b[i - 1][j]

    # print(b)

    s = b[-1]

    ret = 0
    for j in range(60):
        for i, x in enumerate(a, 1):
            if (x >> j) & 1:
                ret = (ret + (1 << j) * ((n - i) - (s[j] - b[i][j]))) % mod
            else:
                ret = (ret + (1 << j) * (s[j] - b[i][j])) % mod
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7
    n = int(input())
    a = tuple(map(int, input().split()))

    b = [0] * 60

    for j in range(60):
        for x in a:
            if (x >> j) & 1:
                b[j] += 1

    ret = 0
    for j in range(60):
        ret = (ret + b[j] * (n - b[j]) * (1 << j)) % mod

    print(ret)


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

import numpy

N = int(input())
A = list(map(int, input().split()))
A_sum = numpy.cumsum(A)

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  for i in range(1,m):
    sum1=A_sum[i-1]
    sum2=sum_left-sum1
    if sum2<sum1:
      break
  if i!=1:
    if sum1-sum2>sum_left-2*A_sum[i-2]:
      sum1=A_sum[i-2]
      sum2=sum_left-sum1
  
  sum_right=A_sum[N-1]-sum_left
  for i in range(m+1,N):
    sum3=A_sum[i-1]-sum_left
    sum4=sum_right-sum3
    if sum4<sum3:
      break
  if i!=m+1:
    if sum3-sum4>sum_right-2*(A_sum[i-2]-sum_left):
      sum3=A_sum[i-2]-sum_left
      sum4=sum_left-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from itertools import accumulate

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

ans=A_sum[N-1]
for m in range(2,N-1):
  sum_left=A_sum[m-1]
  i=bisect_left(A_sum,sum_left/2)
  sum1=A_sum[i]
  if i!=0:
    if A_sum[i]+A_sum[i-1]>sum_left:
      sum1=A_sum[i-1]
  sum2=sum_left-sum1

  sum_right=A_sum[N-1]-sum_left
  i=bisect_left(A_sum,sum_left+sum_right/2)
  sum3=A_sum[i]-sum_left
  if i!=m:
    if A_sum[i]+A_sum[i-1]-2*sum_left>sum_right:
      sum3=A_sum[i-1]-sum_left
  sum4=sum_right-sum3
  max_sum=max(sum1,sum2,sum3,sum4)
  min_sum=min(sum1,sum2,sum3,sum4)
  dif=max_sum-min_sum
  if dif<ans:
    ans=dif

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

a, b, k =  map(int, input().split())
for i in range(a, b+1):
    if a <= i <= (a+k-1) or (b-k+1) <= i <=b:
        print(i)

### FIXED CODE ###

a, b, k =  map(int, input().split())
for i in range(a, min(a+k, b+1)):
    print(i)
for j in range(max(a+k, b-k+1), b+1):
    print(j)
### BUGGY CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
for i in range(N-K+1):
    temp = numpy.sum(p[i:i+K])
    if max < temp:
        max = temp
        maxno = i

exsum = 0

for i in range(K):
    dice = numpy.arange(1, p[i+maxno]+1)
    ex = 0
    p2 = 1/len(dice)

    for x in dice:
        px = p2*x
        ex += px
    exsum += ex
print(exsum)

### FIXED CODE ###

import numpy
N, K = map(int, input().split())
p = numpy.array(list(map(int, input().split())))
max = 0
nowsum = 0
for i in range(N-K+1):
    if i == 0:
        nowsum = numpy.sum(p[i:i+K])
    else:
        nowsum = nowsum - p[i-1] + p[i+K-1]
    if max < nowsum:
        max = nowsum
        maxno = i

exsum = 0

for i in range(K):
    temp = p[i+maxno]
    exsum += (0.5*temp*(temp+1))/temp
print(exsum)
### BUGGY CODE ###

import sys
from bisect import *

input = sys.stdin.readline

N = int(input())
S = input().strip()
M = 998244353

ri = []
gi = []
bi = []

for i, c in enumerate(S):
	if c=='R':
		ri.append(i)
	elif c=='G':
		gi.append(i)
	else:
		bi.append(i)

si = []
mi = []
li = []
for i in range(N):
	tt = [ri[i],gi[i],bi[i]]
	tt.sort()
	si.append(tt[0])
	mi.append(tt[1])
	li.append(tt[2])

ans = 1
for i in range(N):
	st = bisect(si,mi[i])
	lt = bisect(li,mi[i])
	ans *= (st-i)*(i+1-lt)*(i+1)%M

print(ans)

### FIXED CODE ###

import sys
from bisect import *

def main():
	input = sys.stdin.readline

	N = int(input())
	S = input().strip()
	M = 998244353

	ri = []
	gi = []
	bi = []

	for i, c in enumerate(S):
		if c=='R':
			ri.append(i)
		elif c=='G':
			gi.append(i)
		else:
			bi.append(i)

	si = []
	mi = []
	li = []
	for i, tt in enumerate(zip(ri,gi,bi)):
		s, m, l = sorted(tt)
		si.append(s)
		mi.append(m)
		li.append(l)

	ans = 1
	for i, mm in enumerate(mi):
		st = bisect(si,mm)
		lt = bisect(li,mm)
		ans = ans*(st-i)*(i+1-lt)*(i+1)
		ans = ans%M

	print(ans)

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

k, s = map(int, input().split())

cnt = 0

for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                cnt += 1

print(cnt)

### FIXED CODE ###

# coding: utf-8
# Your code here!

k, s = map(int, input().split())

cnt = 0

for i in range(k+1):
    for j in range(k+1):
        if s-i-j <= k and s-i-j>=0:
            cnt += 1

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

from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

N=int(input())
R=[]
C=[]
W=[]

for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    R.append(u-1)
    C.append(v-1)
    W.append(w)
g = coo_matrix((W, (R, C)), shape=(N, N)).tocsr()
d = dijkstra(g, indices=0 ,directed=False, unweighted=False)

for i in d:
    print(int(i) % 2)



### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N = int(input())
for i in range(N-1):
    u, v, w = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, w)
    g.add_edge(v-1, u-1, w)

d = Dijkstra(g, 0)

ans = []
for i in range(N):
    if d.dist[i] % 2 == 0 :
        ans.append(0)
    else:
        ans.append(1)

if sum(ans)==0:
    ans[-1] = 1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

# https://atcoder.jp/contests/abc107/tasks/arc101_a
# C - Candles

n, k = list(map(int, input().split()))
x_list = list(map(int, input().split()))
x_list = sorted(x_list)
min_l = float('inf')
# 0の場所は

for i, x in enumerate(x_list):
    l = 0
    work_list = x_list[i:i+k]
    minus_list = [x for x in work_list if x < 0]
    plus_list = [x for x in work_list if x >= 0]

    if not plus_list:
        l = abs(min(minus_list))
    elif not minus_list:
        l = max(plus_list)
    elif max(plus_list) > max(minus_list):
        l = abs(min(minus_list)) * 2 + max(plus_list)
    else:
        l = max(plus_list) * 2 + abs(min(minus_list))

    if l < min_l:
        min_l = l

    if i + k > n - 1:
        break

print(min_l)

### FIXED CODE ###

# https://atcoder.jp/contests/abc107/tasks/arc101_a
# C - Candles

n, k = list(map(int, input().split()))
x_list = list(map(int, input().split()))
x_list = sorted(x_list)
min_l = float('inf')

minus_list = [x for x in x_list if x < 0]
plus_index = len(minus_list)

for i, x in enumerate(x_list):
    left, right = x_list[i], x_list[i+k-1]
    # 最左端に行ってから、最右端に行く
    a = abs(left) + abs(left-right)
    # 最右端に行ってから、最左端に行く
    b = abs(right) + abs(right - left)
    l = min(a, b)

    if l < min_l:
        min_l = l

    if i + k > n - 1:
        break

print(min_l)
### BUGGY CODE ###

N, K = [int(i) for i in map(int, input().split())]
a = list(map(int, input().split()))
dp = []

for i in range(N):
    dp.append(0)


def mincos(dp, a, i, k):
    if i == 0:
        return 0
    elif i == 1:
        return abs(a[0] - a[1])
    elif i < k:
        cos = []
        for j in range(1, i+1):
            cos.append(dp[i-j]+abs(a[i] - a[i - j]))
        return min(cos)
    else:
        cos = []
        for j in range(1, k+1):
            cos.append(dp[i - j] + abs(a[i] - a[i - j]))
        return min(cos)


for i in range(N):
    dp[i] = mincos(dp, a, i, K)

print(dp[N-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)

for i in range(1, N):
    j = max(0, i-K)
    dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()


print(dp[-1])
### BUGGY CODE ###

n = int(input())
x = input().split(" ")
b_x = [0 for i in range(n)]
for i in range(n):
    x[i] = [int(x[i]), i]
x.sort()
for i in range(n):
    b_x[i] = x[i][1]
for i in range(n):
    if b_x.index(i) < n//2:
            print(x[n//2][0])
    else:
            print(x[n//2-1][0])

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    print(n*800-200*(n//15))

#B
def B():
    k = I()
    ans = 0
    for i in range(1,k):
        for j in range(i+1,k+1):
            if (i%2)^(j%2):
                ans += 1
    print(ans)

#C
def C():
    x,t = LI()
    print(max(0,x-t))

#D
def D():
    n = I()
    ans = 1
    for i in range(1,n+1):
        ans *= i
        ans %= mod
    print(ans)

#E
def E():
    x,y,s,t = LI()
    return

#F
def F():
    n = I()
    x = LI()
    a = sorted(x)
    for i in range(n):
        j = bisect.bisect_left(a,x[i])
        if j >= n//2:
            print(a[n//2-1])
        else:
            print(a[n//2])

#G
def G():
    return

#H
def H():
    return

def J():
    return

def K():
    return

#Solve
if __name__ == "__main__":
    F()
### BUGGY CODE ###

import bisect
x = int(input())
arr = [i**2 for i in range(1,x+1) if i**2 <= x]
ans = bisect.bisect_right(arr, x)
print(arr[ans-1])

### FIXED CODE ###

x = int(input())
print(int(x**0.5)**2)
### BUGGY CODE ###

def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)


# def divbin(s,res):
#   if int(s,2)==0:
#     return
#   # ss=int(s)
#   val=int(s,2)
#   count=bin(val).count("1")
#   val%=count
#   # t_str=bin(str(count))
#   t_str=bin(val)
#   t_str=t_str.replace("0b","")
#   res+=1
#   divbin(t_str,res)
#   return

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  t=deepcopy(x)
  tmp=cnt
  ts=""
  if x[i]=="1":
    cnt-=1
    if i==0:
      ts="0"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"0"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"0"
  else:
    cnt+=1
    if i==0:
      ts="1"+s[i+1:]
    elif 1<=i<len(x)-1:
      ts=s[:i]+"1"+s[i+1:]
    elif i==len(x)-1:
      ts=s[:i]+"1"
  # ans=0
  # global ans
  ans=0
  ans=divbin(ts,ans)
  print(ans)



  # prev=
  # while cnt>0:


    


### FIXED CODE ###

n=int(input())
x=input()
val=int(x,2)

cnt=x.count("1")
p_cnt=cnt+1
m_cnt=cnt-1
p_amari,m_amari=0,0

p_amari=val%(cnt+1)
if cnt-1!=0:
  m_amari=val%(cnt-1)
else:
  m_amari=0

for i in range(n):
  ans=0
  if x[i]=="0":
    amari=p_amari+pow(2,n-i-1,p_cnt)
    amari%=p_cnt
  elif x[i]=="1":
    if cnt-1==0:
      print(0)
      continue
    amari=m_amari-pow(2,n-i-1,m_cnt)
    amari%=m_cnt
  ans+=1
  while amari!=0:
    amari%=bin(amari).count("1")
    ans+=1
  print(ans)
### BUGGY CODE ###

import math
K=int(input())

result=[]
count=0
cnt=0


 
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      cnt+=math.gcd(math.gcd(i,j),k)


print(cnt)

### FIXED CODE ###

from math import gcd
K=int(input())

result=[]
count=0
cnt=0
# def gcd(a,b):
#   while b!=0:
#     a,b=b,a%b
#   return a

 
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      cnt+=gcd(gcd(i,j),k)


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

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[{0}for _ in range(w)]
dp[0]={a[0][0]-b[0][0],b[0][0]-a[0][0]}
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    if i+j:
      x,y=x-y,y-x
      t=set()
      add=t.add
      if i:
        for v in dp[j]:
          add(v+x)
          add(v+y)
      if j:
        for v in dp[j-1]:
          add(v+x)
          add(v+y)
      dp[j]=t
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))
### BUGGY CODE ###

n = int(input())
p = [float(x) for x in input().strip().split()]
dp = [[None for i in range(n//2+2)] for j in range(n)]
for i in range(n):
    dp[i][0] =1

for j in range(n//2+2):
    dp[n-1][j] = 0
dp[n-1][0] = 1
dp[n-1][1] = p[n-1]

for i in range(n-2,-1,-1):
    for j in range(1,n//2+2):
        dp[i][j] = p[i]*dp[i+1][j-1]+(1-p[i])*dp[i+1][j]

print(dp[0][-1])



### FIXED CODE ###

n = int(input())
p = [float(x) for x in input().strip().split()]
dp = [[None for i in range(n//2+2)] for j in range(n)]
for i in range(n):
    dp[i][0] =1

for j in range(n//2+2):
    dp[n-1][j] = 0
dp[n-1][0] = 1
dp[n-1][1] = p[n-1]

for i in range(n-2,-1,-1):
    for j in range(1,n//2+2):
        dp[i][j] = p[i]*dp[i+1][j-1]+(1-p[i])*dp[i+1][j]

print(dp[0][-1])

"""
Recursive top down

# def solve(i,k):
#     # print(i,k)
#     if i<=n-1 and k>0 and dp[i][k]:
#         return dp[i][k]
#     if k<=0:
#         # if i not in dp:
#         #     dp[i] ={}
#         # dp[i][k] = 1
#         return 1

#     elif i>n-1:
#         # if i not in dp:
#         #     dp[i] ={}
#         # dp[i][k] = 0
#         return 0
#     elif k>n-i:
#         # if i not in dp:
#         #     dp[i] ={}
#         dp[i][k] = 0

#     else:
#         # if i not in dp:
#         #     dp[i] ={}
#         dp[i][k] = p[i]*solve(i+1,k-1)+(1-p[i])*solve(i+1,k)
#     return dp[i][k]


# print(solve(0,n//2+1))


"""
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
ans=sum(P[:K])/2+0.5*K
for i in range(N-K+1):
    _sum=sum(P[i:i+K])/2+0.5*K
    if ans<_sum:
        ans=_sum
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
ans=sum(P[:K])/2+0.5*K
A,S=[0]*N,[0]*N
A[0]=S[0]=P[0]
for i in range(N-1):
    A[i+1]=P[i+1]
    S[i+1]=S[i]+A[i+1]

for i in range(N-K):
    tmp=(S[K+i]-S[i])/2+0.5*K
    if ans<tmp:
        ans=tmp
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

H,W=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ set() for _ in range(W) ] for __ in range(H) ]

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)
dp[r][c].add(val*-1)

D=[(1,0),(0,1)]

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                next_r=r+dr
                next_c=c+dc
                next_val=A[next_r][next_c]
                for j in dp[r][c]:
                    dp[next_r][next_c].add(j+next_val)
                    dp[next_r][next_c].add(j+next_val*-1)

print min(map(lambda x: abs(x), dp[H-1][W-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque,defaultdict

H,W=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ 0 for _ in range(W) ] for __ in range(H) ]

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]
Visit=defaultdict(lambda: 0)     #訪問済みの頂点にフラグ1を立てる
Visit[(0,0)]=1
D=[(1,0),(0,1)]

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                next_r=r+dr
                next_c=c+dc
                next_val=A[next_r][next_c]
                dp[next_r][next_c]|=dp[r][c]<<next_val  #次のマスの値が+の場合は、bitshift全体を左にシフト
                dp[next_r][next_c]|=dp[r][c]>>next_val  #次のマスの値が-の場合は、bitshift全体を右にシフト
                q.append((next_r,next_c))

ans=float("inf")
for i in range(Center*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans