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

from collections import deque



def main():
    h,w=map(int,input().split())
    w+=2

    a=[list('@'*w)]
    for i in range(h):
        a+=[list('@'+input()+'@')]
    a+=[list('@'*w)]
    h+=2

    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que=deque()



    A=[[float('inf')]*w for i in range(h)]

    for i in range(1,h-1):
        for j in range(1,w-1):
            if a[i][j]=='#':
                A[i][j]=0
                que.append((i,j))


    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)

    print(res)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
w+=2

a=[list('@'*w)]
for i in range(h):
    a+=[list('@'+input()+'@')]
a+=[list('@'*w)]
h+=2

xy=[(-1,0),(0,-1),(0,1),(1,0)]
que=deque()

def bfs():
    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)
    return res


A=[[float('inf')]*w for i in range(h)]

res=0
for i in range(1,h-1):
    for j in range(1,w-1):
        if a[i][j]=='#':
            A[i][j]=0
            que.append((i,j))

res=bfs()
print(res)
### BUGGY CODE ###

#import heapq
n, m = map(int, input().split())
lst = list(map(int, input().split()))
for i in range(m):
  lst[lst.index(max(lst))] //= 2
print(sum(lst))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
lst = list(map(lambda x:-1*int(x), input().split()))
heapq.heapify(lst)
for i in range(m):
  heapq.heappush(lst, -(-heapq.heappop(lst)//2))
print(-1*sum(lst))
### BUGGY CODE ###

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

def kitaichi(n):
	ret = 0
	for i in range(n+1):
		ret += i
	return ret / n

ans = 0
for i in range(len(p)):
	pp = p[i:i+k]
	if len(pp) != k: break
	tmp = 0
	for j in pp:
		tmp += kitaichi(j)
	ans = max(ans, tmp)


print(ans)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = [-~int(i)/2 for i in input().split()]
a = [0] + list(accumulate(p))
print(max(j-i for i, j in zip(a, a[k:])))
### BUGGY CODE ###

import sys
n = int(input())
s = list(input())
a_li = []
b_li = []
c_li = []
for i,ss in enumerate(s):
    if ss == 'R':
        a_li.append(i)
    elif ss == 'G':
        b_li.append(i)
    else:
        c_li.append(i)
if len(a_li) == 0 or len(b_li)== 0 or len(c_li) == 0:
    print(0)
    sys.exit()
all_count = 0
for a in a_li:
    for b in b_li:
        tmp = len(c_li)
        lili = []
        if (2*b - a)  in c_li:
            lili.append(2*b - a)
            #tmp -= 1
        if (2*a - b)  in c_li:
            lili.append(2*a - b)
            #tmp -= 1
        if (a + b)% 2 == 0 and (a + b)//2   in c_li:
            lili.append((a + b)//2)
            #tmp -= 1
        tmp -= len(set(lili))
        all_count += tmp
print(all_count)

### FIXED CODE ###

n = int(input())
s = list(input())
a_li = []
b_li = []
c_li = []
for i,ss in enumerate(s):
    if ss == 'R':
        a_li.append(i+1)
    elif ss == 'G':
        b_li.append(i+1)
    else:
        c_li.append(i+1)
count = 0
for i in range(1,n+1):
    for d in range(1,n):
        if i + 2*d > n:
            break
        if s[i-1] != s[i+d-1] and s[i+d-1] != s[i+2*d-1] and s[i-1] != s[i+2*d-1]:
            count += 1
#print(len(a_li),len(b_li),len(c_li),count)
#print(count)
print(len(a_li)*len(b_li)*len(c_li)-count)
### BUGGY CODE ###

N=int(input())
a=4/N
for h in range(1,3501):
    H=1/h
    for n in range(h,3501):
        flag=0
        if a-H-1/n-1<=0 and a-H-1/n-1/3500>=0:

            st,end=1,3500
            for w in [st,end]:
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    break
            while st!=end:
                #print(h,n,st,end)
                w=int((st+end)/2)
                if end-st==1:
                    end=w
                    st=w
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
                elif B>0:
                    end=w
                else:
                    st=w

        if flag:
            break
    if flag:
        break

print(h,n,w)


### FIXED CODE ###

N=int(input())
a=4/N
h_st=max(int(N*(1/4))-1,1)
#h_st=1
for h in range(h_st,3501):
    H=1/h
    for n in range(h,3501):
        flag=0
        if 4*h*n*n-(n*n+h*n+h*n)*N<=0 and 4*h*n*3500-(n*3500+h*3500+h*n)*N>=0:

            st,end=n,3500
            for w in [st,end]:
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
            while st!=end:
                #print(h,n,st,end)
                w=int((st+end)/2)
                if end-st==1:
                    end=w
                    st=w
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
                elif B>0:
                    end=w
                else:
                    st=w

        if flag:
            break
    if flag:
        break

print(h,n,w)
### BUGGY CODE ###

K = int(input())
a = 0
n = 0
out = -1
while True:
  a += 7 * (10 ** n)
  if a % K == 0:
    out = n + 1
    print(out)
    break
  n += 1

### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect.bisect_left(l[j+1:],l[i]+l[j])
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = list(map(int,input().split()))
import bisect
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect.bisect_left(l,l[i]+l[j]) - j - 1
print(count)
### BUGGY CODE ###

import math
L, R = map(int, input().split())
i = L
min = 2020
while(i < R):
  j = i + 1
  while(j <= R):
    tmp = i * j % 2019
    if(min > tmp):
      min = tmp
    j += 1
  i += 1
print(min)

### FIXED CODE ###

import math
L, R = map(int, input().split())
if (R - L + 1) > 673:
  print(0)
else:
  i = L
  min = 2020
  while(i < R):
    j = i + 1
    while(j <= R):
      tmp = i * j % 2019
      if(min > tmp):
        min = tmp
      j += 1
    i += 1
  print(min)
### BUGGY CODE ###

k = int(input())

sum = 0

def gcd(x, y): # ユークリッドの互除法
    if y > x:
        y,x = x,y
    while y > 0:
        r = x%y
        x = y
        y = r
    return x

for i in range(1,k+1):
    for m in range(1,k+1):
        for l in range(1,k+1):
            sum += gcd(gcd(i,m),l)
print(sum)


### FIXED CODE ###

k = int(input())

sum = 0

def gcd(x, y): # ユークリッドの互除法
    if y > x:
        y,x = x,y
    while y > 0:
        r = x%y
        x = y
        y = r
    return x

import math

for i in range(1,k+1):
    for m in range(1,k+1):
        sub = gcd(i,m)
        for l in range(1,k+1):
            sum += gcd(sub,l)
print(sum)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ok = 0
for r in range(N // R + 1):
    for g in range(N // G + 1):
        last_num = N - (r * R) - (g * G)
        if last_num >= 0 and last_num % B == 0:
            ok += 1

print(ok)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ok = 0
for r in range(N // R + 1):
    for g in range((N - r * R) // G + 1):
        last_num = N - (r * R) - (g * G)
        if last_num >= 0 and last_num % B == 0:
            ok += 1

print(ok)
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
c = []
for i in range(n):
    a, b = map(int, input().split())
    c += [a]*min(b,m)
c.sort()
print(sum(c[:m]))

### FIXED CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ab = []
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab)
for c, d in ab:
    if m >= d:
        ans += c*d
        m -= d
    else:
        ans += c*m
        break
print(ans)
### BUGGY CODE ###

"""
AtCoder :: M-Solutions Programming Contest 2020 :: Marks
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c
"""
import sys
from functools import reduce
from operator import mul


def solve(A, K):
    """Solve puzzle."""
    solns = []
    grade = reduce(mul, A[:K])
    for i in range(K, len(A)):
        grade0 = (grade // A[i-K]) * A[i]
        if grade0 > grade:
            solns.append('Yes')
        else:
            solns.append('No')
        grade = grade0
    return(solns)


def main():
    """Main program."""
    N, K = (int(i) for i in sys.stdin.readline().split())
    A = [int(i) for i in sys.stdin.readline().split()]
    print("\n".join(solve(A, K)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

"""
AtCoder :: M-Solutions Programming Contest 2020 :: Marks
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_c
"""
import sys
from functools import reduce
from operator import add
from math import log


def solve(A, K):
    """Solve puzzle."""
    solns = []
    grade = reduce(add, A[:K])
    for i in range(K, len(A)):
        grade0 = (grade - A[i-K]) + A[i]
        if grade0 > grade:
            solns.append('Yes')
        else:
            solns.append('No')
        grade = grade0
    return(solns)


def main():
    """Main program."""
    N, K = (int(i) for i in sys.stdin.readline().split())
    A = [log(float(i)) for i in sys.stdin.readline().split()]
    print("\n".join(solve(A, K)))


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

acgt = ['A','C','G','T']
N, Q = map(int, input().split())
S = list(input())
for _ in range(Q):
    cnt = 0
    li, ri = map(int, input().split())
    tmpS = S[li-1:ri]
    i = 1
    while i < len(tmpS):
        if tmpS[i] == 'C':
            if tmpS[i - 1] == 'A':
                cnt += 1
        i += 1
    print(cnt)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

cnt = 0
tmpS = S
i = 1
L = [0]
lapp = L.append
while i < N:
    t = tmpS[i]
    if t == 'A':
        lapp(cnt)
        i += 1
    elif t == 'C':
        if tmpS[i-1] == 'A':
            cnt += 1
        lapp(cnt)
        lapp(cnt)
        i += 2
    else:
        lapp(cnt)
        lapp(cnt)
        i += 2
for _ in range(Q):
    li, ri = map(int, input().split())
    print(L[ri - 1] - L[li - 1])
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
h=np.array(input().split(), dtype=int)
dp=np.zeros(n, dtype=int)
dp=[0]*n
for i in range(1, n):
    left=max(0, i - k)
    dp[i]=min(abs(h[i]-h[left:i])+dp[left:i])
print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
H = [int(x) for x in input().split()]
 
def main(N,K,H):
    dp = [0]*N
    for i in range(1,N):
        L = [dp[j]+abs(H[i]-H[j]) for j in range(max(0,i-K),i)]
        dp[i] = min(L)
    print(dp[-1])
main(N,K,H)
#自分のコードがTLEになるので、他の人が書いたコードでAC出来るのか確認。
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
li = sorted(li)
count = 1
if  not (1 in li and 0 in li) :
    count = 0
else:
    for i in range(2,max(li) + 1):
        a = li.count(i-1)
        b = li.count(i)
        count *= a ** b
print(count % 998244353)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
box = [0 for x in range(max(li)+1)]
for i in li:
    box[i] += 1
count = 1

if len(box) > 2:
    for i in range(1, len(box)-1):
        count *= box[i] ** box[i+1]
        count %= 998244353
else:
    count = 1
    
if box[0] != 1 or li[0] != 0:
    count = 0

print(count % 998244353)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()

ans = 0

for i in range(1, n+1):
    for j in range(n-i+1):
        if int(s[j:j+i]) % p == 0:
            ans += 1


print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
s = input()

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        m10 = (10 * m10) % p
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

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

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a-1,b-1)
    L = uf.all_group_members().values()
    ans = 1
    for l in L:
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a - 1, b - 1)
    print(-min(uf.parents))


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

K,S=map(int,input().split())
ans=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:
        ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
def als(n):
  if 0<=n<=k:
    return n+1
  elif k+1<=n<=2*k:
    return 2*k+1-n
  else:
    return 0
for i in range(k+1):
  ans+=als(s-i)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [sorted(input()) for _ in  range(n)]

ans = 0
for i,moji in enumerate(s):
    for j in range(n-i-1):
        if moji == s[i+j+1]:
            ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
sl ={}
ans = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in sl:
        sl[s] +=1
    else:
        sl[s] =1
for i in sl.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
S = []
for i in range(M):
  B,C = map(int, input().split())
  for j in range(B):
    heappush(S,-C)
heapify(A)
i = 0
l = len(S)
while i < min(N,l):
  a = heappop(A)
  q = -1*heappop(S)
  if a < q:
    heappush(A,q)
    i += 1
  else:
    heappush(A,a)
    break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
As = list(map(int, input().split()))

c = collections.Counter(As)

sum_ = 0
for key, val in c.items():
  sum_ += (val*(val-1)/2)

sum_ = int(sum_)

dic = {}
for i in list(set(As)):
  dic[i] = As.count(i)-1
      
for i in range(N):
  print(sum_-dic[As[i]])

### FIXED CODE ###

import collections
N = int(input())
As = list(map(int, input().split()))

c = collections.Counter(As)

sum_ = 0
for key, val in c.items():
  sum_ += (val*(val-1)/2)

sum_ = int(sum_)

for i in range(N):
  print(sum_-(c[As[i]]-1))
### BUGGY CODE ###


import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    for a in A:
        P.append(a)
            
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()






    for i in A:
        tmp=[]
        for j in sosus:
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        print('setwise coprime')
    else:
        print('not coprime')

resolve()


### FIXED CODE ###


import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        A = [i for i in A if i%prime!=0]

    P.extend(A)
          
    return P


def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    sosus = set(get_primes(max(A)+1))
    dvd = set()



    val = A[0]
    for i in A:
        val = math.gcd(i,val)

    if val ==1:
        pass
    else:
        print('not coprime')
        return

    for i in A:
        tmp=[]
        for j in sosus:
            if j>i:
                break
            if i % j ==0:
                tmp.append(j)
                while i % j ==0:
                    i //=j
            if i ==1:
                break
            if i in sosus:
                
                tmp.append(i)
                i = 1
                break
        sosus.difference_update(tmp)
        
        if i != 1:
            break
    else:
        print('pairwise coprime')
        return

    print('setwise coprime')

resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edges = []
# edges = [[] for _ in range(N)]
sum_w = 0
for i in range(N-1):
    u, v, w = map(int, input().split())
    edges.append([u-1,v-1,w])

    # edges[u-1].append([v-1,w])
    # edges[v-1].append([u-1,w])


dist = [None]*N
dist[0] = 0

while len(edges) > 0:
    for edge in edges:
        if dist[edge[0]] == None and dist[edge[1]] != None:
            dist[edge[0]] = dist[edge[1]] + edge[2]
            edges.remove(edge)
        elif dist[edge[1]] == None and dist[edge[0]] != None:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            edges.remove(edge)

for item in dist:
    print(item%2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    tree[u-1].append([v-1,w])
    tree[v-1].append([u-1,w])

dist = [None]*N
dist[0] = 0
comp = [0]*N
next_ptr = [0]
for ptr in next_ptr:
    comp[ptr] = 1
    edges = tree[ptr]
    for edge in edges:
        if comp[edge[0]] == 0:
            dist[edge[0]] = dist[ptr] + edge[1]
            next_ptr.append(edge[0])

for item in dist:
    print(item%2)
### BUGGY CODE ###

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

money = 1000
stock = 0
for i in range(N - 1):
    if A[i] == A[i + 1]:
        continue
    elif A[i] > A[i + 1]:
        while stock > 0:
            money += A[i]
            stock -= 1
    elif A[i] < A[i + 1]:
        while money >= A[i]:
            money -= A[i]
            stock += 1
while stock > 0:
    money += A[N - 1]
    stock -= 1

print(money)

### FIXED CODE ###

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

money = 1000
stock = 0
for i in range(N - 1):
    if A[i] == A[i + 1]:
        continue
    elif A[i] > A[i + 1]:
        money += A[i] * stock
        stock = 0
    elif A[i] < A[i + 1]:
        buy = money // A[i]
        money -= A[i] * buy
        stock += buy
money += A[N - 1] * stock
stock = 0

print(money)
### BUGGY CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
d = []
heapify(d)
heappush(d,(0,sh,sw))

while len(d)>0:
  cnt,h,w = heappop(d)
  if visited[h][w]<=cnt:
    continue
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        heappush(d,(cnt,h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        heappush(d,(cnt+1,h2,w2))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)