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

def solve(N, As, Bs, Cs):
    # print(As, Bs, Cs)
    ans = 0
    As.sort()
    Bs.sort()
    Cs.sort()
    memo = {}
    for a in As:
        for b in Bs:
            if b <= a:
                continue
            if b in memo:
                ans += memo[b]
                continue
            bans = 0
            for i, c in enumerate(Cs):
                if b < c:
                    bans += N - i
                    break
            memo[b] = bans
            ans += bans
    return ans


if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))
    Bs = list(map(int, input().split(" ")))
    Cs = list(map(int, input().split(" ")))
    print(solve(N, As, Bs, Cs))


### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect_right(C, b)
    ans += i * (N - j)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

"""
ABC113_C ID 学び：
 python の0埋め　s.rjust(digit,0) でいける
 sortを県ごとにしないといけない、とわかれば、input, sort , outputの３段かいに別れる
どんな配列を持てばいいかは事前に考える。
実際にそこまで立てて、inputをローカルでやると良い
"""

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, m = map(int, input().split())
lis_p = [[] for _ in range(n)]  # 県pに属する市の誕生年が入る
city = [[0, 0] for _ in range(m)]  # p と　idx
idx_p = []  # 何番目にそのcity が県pに追加されたかを記憶
# input
for i in range(m):
    p, y = map(int, input().split())
    city[i][0] = p - 1
    city[i][1] = len(lis_p[p - 1])
    lis_p[p - 1].append(y)
for pref in range(n):
    k = len(lis_p[pref])
    # print(lis_p[pref])
    idx = []
    if k > 0:
        lis_p[pref], idx = zip(*sorted(zip(lis_p[pref], range(k))))
    idx_p.append(list(idx))
#print(lis_p, idx_p)
for i in range(m):
    # string になおす必要がある rjust
    print(str(city[i][0] + 1).rjust(6, "0"), end="")
    print(str(1 + idx_p[city[i][0]].index(city[i][1])).rjust(6, "0"))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import bisect

"""
ABC113_C ID 学び：
 python の0埋め　s.rjust(digit,0) でいける
 sortを県ごとにしないといけない、とわかれば、input, sort , outputの３段かいに別れる
どんな配列を持てばいいかは事前に考える。
実際にそこまで立てて、inputをローカルでやると良い
"""

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, m = map(int, input().split())
lis_p = [[] for _ in range(n)]  # 県pに属する市の誕生年が入る
city = [[0, 0] for _ in range(m)]  # p と　idx
idx_p = []  # 何番目にそのcity が県pに追加されたかを記憶
# input
for i in range(m):
    p, y = map(int, input().split())
    city[i][0] = p - 1
    city[i][1] = y
    lis_p[p - 1].append(y)
for pref in range(n):
    k = len(lis_p[pref])
    # print(lis_p[pref])
    idx = []
    if k > 0:
        lis_p[pref], idx = zip(*sorted(zip(lis_p[pref], range(k))))
    idx_p.append(list(idx))
# print(lis_p, idx_p)
for i in range(m):
    # string になおす必要がある rjust
    print(str(city[i][0] + 1).rjust(6, "0"), end="")
    print(str(1 + bisect.bisect_left(lis_p[city[i][0]], city[i][1])).rjust(6, "0"))
### BUGGY CODE ###

def main():
    import numpy as np
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = np.zeros(c+1, dtype=np.int64)
    dp[0] = 1
    p = np.array([[pow(j, i, mod) for j in range(401)]
                  for i in range(401)], dtype=np.int64)
    for a, b in zip(A, B):
        q = np.sum(p[:, a:b+1], axis=1) % mod
        dp = [sum(dp[i::-1]*q[:i+1] % mod) % mod for i in range(c+1)]
    print(dp[-1] % mod)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0

    p = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        q = [0]*(c+1)
        for i in range(c+1):
            q[i] = sum(p[i][a:b+1]) % mod
        for i in range(c+1):
            temp = 0
            for j in range(i+1):
                temp += dp[i-j]*q[j]
            dp2[i] = temp % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()
### BUGGY CODE ###

loop = int(input())
num_list = list(map(int, input().split()))
ans = 0
for idx, n in enumerate(num_list):
  flg = True
  if idx > 0:
    for m in num_list[: idx]:
      if m < n:
        flg = False
        break
  if flg:
    ans += 1
print(ans)

### FIXED CODE ###

loop = int(input())
num_list = list(map(int, input().split()))
ans = 0
min_value = 20000000
for n in num_list:
  flg = True
  if min_value < n:
    flg = False
  else:
    min_value = n
  if flg:
    ans += 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]
for i in range(N):
    sumA.append(sumA[i] + A[i])
for i in range(M):
    sumB.append(sumB[i] + B[i])

#print(sumA)
    
#sumA = list(itertools.accumulate(A))
#sumB = list(itertools.accumulate(B))
ans=0
j=M
for i in range(N+1):
    if sumA[i]>K:
        break
    #j-=1
    while K<sumA[i]+sumB[j] and j>=0:
        j-=1
    if i==0:
        best=j
    ans=max(ans,i+j)
    j=best
print(ans)

### FIXED CODE ###

import itertools

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

sumA = list(itertools.accumulate(A))
sumB = list(itertools.accumulate(B))
j=M-1
while K<sumB[j] and j>=0:
    j-=1
ans=j+1
for i in range(N):
    if sumA[i]>K:
        break
    while K<sumA[i]+sumB[j] and j>=0:
        j-=1
    ans=max(ans,i+j+2)
print(ans)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a = list(reversed(sorted(a)))
b = list(reversed(sorted(b)))
c = list(reversed(sorted(c)))
ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if i * j * l <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break
ans = list(reversed(sorted(ans)))
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

import numpy as np

from numba import njit


# def pg(aaa):
#     for i in range(0, n2 ** 2, n2):
#         print(aaa[i:i + n2])
#     print()

@njit
def solve(n, ppp):
    n2 = n + 2
    row_base = [0] * n
    for i in range(n):
        row_base[i] = min(i, n - 1 - i)

    seats = [-1] * (n2 * n2)
    is_seated = [False] * (n2 * n2)
    for i in range(n):
        ud = min(i, n - 1 - i)
        for j in range(n):
            ij = (i + 1) * n2 + j + 1
            seats[ij] = min(ud, row_base[j])
            is_seated[ij] = True

    ans = 0
    MOVE = (-n2, -1, 1, n2)

    for p in ppp:
        i, j = divmod(p - 1, n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = False

        q = [(res, i)]
        updated = set()

        while q:
            val, j = heappop(q)
            if j in updated:
                continue
            updated.add(j)
            seats[j] = val
            if is_seated[j]:
                val += 1
            for dj in MOVE:
                nj = j + dj
                if seats[nj] > val and nj not in updated:
                    heappush(q, (val, nj))
        # print(p, i, res)
        # pg(seats)

    print(ans)


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32)
solve(n, ppp)


### FIXED CODE ###

import sys
import numpy as np

from numba import njit


@njit('i4(i4,i4[:])', cache=True)
def solve(n, ppp):
    n2 = n + 2
    nsq = n2 * n2
    seats = np.zeros(nsq, dtype=np.int16)
    is_seated = np.zeros(nsq, dtype=np.int8)
    for i in range(n):
        ud = min(i, n - 1 - i)
        ri = (i + 1) * n2
        for j in range(n):
            ij = ri + j + 1
            seats[ij] = min(ud, j, n - 1 - j)
            is_seated[ij] = 1

    MOVES = np.array([-n2, -1, 1, n2], dtype=np.int32)

    ans = 0

    for pi in range(n * n):
        i, j = divmod(ppp[pi], n)
        i = (i + 1) * n2 + j + 1
        res = seats[i]
        ans += res
        is_seated[i] = 0

        q = []
        for mi in range(4):
            ni = i + MOVES[mi]
            if seats[ni] > res:
                seats[ni] = res
                q.append(ni)

        while q:
            j = q.pop()
            # print(val, j, seats[j], l, r)
            val = seats[j]

            if is_seated[j]:
                val += 1
            for mi in range(4):
                nj = j + MOVES[mi]
                if seats[nj] > val:
                    seats[nj] = val
                    q.append(nj)

        # print(ppp[pi] + 1, i, ans)
        # print(seats.reshape((n2, n2)))
        # print(is_seated.reshape((n2, n2)))

    return ans


n = int(sys.stdin.buffer.readline())
ppp = np.array(list(map(int, sys.stdin.buffer.read().split())), dtype=np.int32) - 1

# n = 20
# np.random.seed(seed=32)
# ppp = np.random.permutation(n * n).astype(np.int32)
# print(ppp)

print(solve(n, ppp))
### BUGGY CODE ###

N = int(input()) 
s = [input() for i in range(N)]
LIS=[]
for i in range(N):
  LIS.append(''.join(sorted(s[i])))
n=0
set1=set(LIS)
for str in set1:
  m=LIS.count(str)
  n+=m*(m-1)/2
print(int(n))

### FIXED CODE ###

N = int(input()) 
s = [input() for i in range(N)]
LIS=[]
for i in range(N):
  LIS.append(''.join(sorted(s[i])))
LIS.sort()
n=0
prestr=LIS[0]
count=1
for st in LIS[1:]:
  if st==prestr:
    n+=count
    count+=1
  else:
    count=1
    prestr=st
print(int(n))
### BUGGY CODE ###

k, s = map(int, input().split(' '))
r = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        for z in range(0, k + 1):
            if x + y + z == s:
                r += 1
print(r)

### FIXED CODE ###

k, s = map(int, input().split(' '))
r = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        if s - x - y <= k and s - x - y >= 0:
            r += 1
print(r)
### BUGGY CODE ###

import numpy as np
from numba import njit

@njit
def solve(n, k, l):
    if k >= 50:
        k = 50
    
    dp= [[0,0]]
    for i in range(n-1):
        dp += [[0]*2]
    
    ans = l[:]
    
    for i in range(k):
        for j in range(n):
            tmp = ans[j]
            dp[j][0] = (j+1 - tmp)
            dp[j][1] = (j+1 + tmp)
    
        ans = [0] * n
    
        for x in range(n):
            for y in range(n):
                if dp[y][0] <= x+1 <= dp[y][1]:
                    ans[x] += 1
    
    else:
        return ans

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

print(*solve(n,k,l))



### FIXED CODE ###

import numpy as np
from numba import njit

@njit #処理の並列化

def imos(n, a):
    
    l=np.zeros((n+1), dtype = np.int64)

    for i in range(n):
        ai = a[i] # 光の強さ_これにより照らせる範囲が決まる
        start = max(0, i - ai) #StartIndex_照らせる範囲
        end = min(n, i + ai + 1) #EndIndex + 1_照らせる範囲
        l[start] += 1 # 各々を'+1'と'-1'で表し...
        l[end] -= 1
    return np.cumsum(l)[:n] # 累積和をとる_cumulative sum

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

for _ in range(k):
    a = imos(n, a)
    if a.min() == n: # すべての要素が最大値'n'になるとbreak
        break

print(*a)
### BUGGY CODE ###

n, k = map(int, input().split())
hlis = list(map(int, input().split()))
dp = [0] + [float('inf')]*(n-1)
for i in range(1, n):
    l = 1
    while i-l >= 0 and l <= k:
        dp[i] = min(dp[i], dp[i-l]+abs(hlis[i-l] - hlis[i]))
        l += 1
print(dp[n-1])

### FIXED CODE ###

N, K = map(int, input().split())
hlis = list(map(int, input().split()))
dp = [float('inf')]*(N+1)
dp[1] = 0
for i in range(1, N):
    for j in range(1,min(K+1, N-i+1)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(hlis[i-1]-hlis[i+j-1]))
print(dp[-1])
### BUGGY CODE ###

from itertools import permutations
n = int(input())
a = tuple(map(int, input().split()))
l = [i + 1 for i in range(n)]
mod = (10**9 + 7)
ans = 0
for v in permutations(l):
    check = [l]
    for i in v:
        for lis in check:
            temp = lis
            if i in temp:
                for k in temp:
                    ans += a[k-1]%mod
                left = temp[:temp.index(i)]
                right = temp[temp.index(i)+1:]
                check.remove(temp)
                check.append(left)
                check.append(right)
                break
            else:
                continue
print(ans%mod)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
#10**9+7を法とする
mod = 10**9 + 7
#1/{abs(i-j)+1}の累積和をxで考える
x = [0]
#permutation
p = 1
ans = 0
#modの逆元として累積和を考える
for i in range(n):
    x.append((x[-1]+pow(i+1, mod-2, mod))%mod)
    p = (p*(i+1))%mod
#1/{abs(i-j)+1}の累積和はi = j で符号変化に注意
#1はダブルカウントしているので引く
for i in range(n):
    ans = (ans + a[i]*(x[i+1]+x[n-i]-1))%mod
#いま求めたのは1回あたりの期待値なのでn!回考える
print((ans*p)%mod)
### BUGGY CODE ###


n, k = [int(i) for i in input().split()]

cnt = 0
for i in range(1,2*n//k+1):
    for j in range(1, min(k*i, n+1)):
        a = j
        b = k*i-a
        if b <= n and (b-a)%k == 0:
            cnt += (a+n)//k- a//k
print(cnt)


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
cnt = 0
if K % 2 == 0:
    for i in range(1, 2*N//K+1):
        cnt += 1 + (2*N//K-i)//2 * 6 + (2*N//K-i)//2 * ((2*N//K-i)//2 - 1) * 3
else:
    for i in range(1, N//K+1):
        cnt += 1 + (N//K-i) * 6 + (N//K-i) * ((N//K-i) - 1) * 3

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

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))

for i in range(M):
    # list_A.sort(reverse=True)
    idx_max = list_A.index(max(list_A))
    list_A[idx_max] = int(list_A[idx_max]/2) 

ans = 0

for i in range(N):
    ans += list_A[i]

print(ans)


### FIXED CODE ###

import sys
import math
import numpy as np
from fractions import gcd

import heapq

# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

N,M = map(int, sys.stdin.readline().split())
list_A = list(map(int, sys.stdin.readline().split()))
# list_A.sort(reverse=True)

# list_A_np = np.array(list_A)

# hq = heapq.heapify(list_A)
for i in range(N):
    list_A[i] = -list_A[i]

heapq.heapify(list_A)
# print(list_A)
# print(int(-4.34))

for i in range(M):
    tmp = heapq.heappop(list_A)
    heapq.heappush(list_A, int(tmp/2))

# for i in range(M):
    # list_A.sort(reverse=True)
    # idx_max = list_A.index(max(list_A))
    # list_A[idx_max] = int(list_A[idx_max]/2)

    # if(list_A[0] > list_A[1]):
    #     list_A[0] = int(list_A[0]/2)
    # else:
    #     list_A.sort(reverse=True)
    #     list_A[0] = int(list_A[0]/2)


    # if(list_A_np[0] > list_A_np[1]):
    #     list_A_np[0] = int(list_A_np[0]/2)
    # else:
    #     # idx_max = list_A_np.argmax()
    #     # list_A_np[idx_max] = int(list_A_np[idx_max]/2)
    #     list_A_np = np.sort(list_A_np)[::-1]
    #     list_A_np[0] = int(list_A_np[0]/2)

    # idx_max = list_A_np.argmax()
    # list_A_np[idx_max] = int(list_A_np[idx_max]/2)

ans = 0

for i in range(N):
    # ans += list_A[i]
    # ans += list_A_np[i]
    # ans += hq.pop
    ans += heapq.heappop(list_A)

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

n = int(input().strip())

ans=0
cnt=[0]*n
for divisor in range(1,n+1):
    mult=divisor
    while mult<=n:
        cnt[mult-1]+=1
        mult+=divisor
for i,v in enumerate(cnt):
    ans+=(i+1)*v
print(ans)

### FIXED CODE ###

n = int(input().strip())

ans=0
for divisor in range(1,n+1):
    ans+=divisor*(n//divisor*(n//divisor+1)//2)

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

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

l=[[0,0] for i in range(N*M+1)]

for a in A:
    if l[a][0]==1:
        print(0)
        exit()
    l[a][0]+=1
for b in B:
    if l[b][1]==1:
        print(0)
        exit()
    l[b][1]+=1

A=0
B=0
ans=1

for i in range(N*M):
    n=N*M-i
    if l[n]==[1,1]:
        A+=1
        B+=1
    elif l[n]==[1,0]:
        A+=1
        ans*=B
    elif l[n]==[0,1]:
        B+=1
        ans*=A
    else:
        ans*=A*B-(N*M-n)

print(ans%(10**9+7))


### FIXED CODE ###

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

l=[[0,0] for i in range(N*M+1)]

for a in A:
    if l[a][0]==1:
        print(0)
        exit()
    l[a][0]+=1
for b in B:
    if l[b][1]==1:
        print(0)
        exit()
    l[b][1]+=1

A=0
B=0
ans=1

for i in range(N*M):
    n=N*M-i
    if l[n]==[1,1]:
        A+=1
        B+=1
    elif l[n]==[1,0]:
        A+=1
        ans*=B
    elif l[n]==[0,1]:
        B+=1
        ans*=A
    else:
        ans*=A*B-(N*M-n)

    ans%=10**9+7

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

N = int(input())
X = list(map(int,input().split()))
for i in range(N):
    A = X[:i] + X[i+1:]
    A.sort()
    print(A[(N-1)//2])

### FIXED CODE ###

import copy
N = int(input())
X = list(map(int,input().split()))
Y = copy.copy(X)
X.sort()
index = N//2
for i in range(N):
    print(X[index] if X[index]>Y[i] else X[index-1])
### BUGGY CODE ###

n = int(input())

XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    # 矛盾したらFalse 正直者と仮定した証言より 正直&正直者と仮定されている / 不親切&不親切と仮定されている True
    if ((i >> xiyj) & 1) ^ HoU:
        return False

    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    honest = [0] * len(XY)
    is_contradiction = True
    for j in range(len(XY)):
        # 正直者と仮定したときだけ採用
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False

    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)

### FIXED CODE ###

n = int(input())
 
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    # 矛盾したらFalse 正直者と仮定した証言より 正直&正直者と仮定されている / 不親切&不親切と仮定されている True
    if ((i >> xiyj) & 1) ^ HoU:
        return False
 
    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    honest = [0] * len(XY)
    is_contradiction = True
    for j in range(len(XY)):
        # 正直者と仮定したときだけ採用
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
 
    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]

stack = deque()
stack.append([ch-1,cw-1])
INF=10**8
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)