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

x = int(input())
if x == 1:
  print(0,-1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(x)
for div in divisorize(fct):
    c.append(num(div))
    
chk = False
for s in c:
  if chk:
    break
  for i in range(1000):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  if s <1000:    
    for p in range(s,1000):
      j = -1*p
      #print(s,(j+s)**5-j**5)
      if (j+s)**5-j**5 > x:
        break 
      if (j+s)**5-j**5 == x:
        ans = (j+s,j)
        chk = True
        break 
  for ww in range(1,(s+1)//2):
    jj = -1*ww
    if (jj+s)**5-jj**5 == x:
      ans = (jj+s,jj)
      chk = True
      break 
print(*ans)

### FIXED CODE ###

x = int(input())
if x == 1:
  print(0,-1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(x)
for div in divisorize(fct):
    c.append(num(div))
    
chk = False
for s in c:
  if chk:
    break
  for i in range(1000):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  if s <1000:    
    for p in range(s,1000):
      j = -1*p
      #print(s,(j+s)**5-j**5)
      if (j+s)**5-j**5 > x:
        break 
      if (j+s)**5-j**5 == x:
        ans = (j+s,j)
        chk = True
        break 
  for ww in range(1,(s+1)//2)[::-1]:
    jj = -1*ww
    if (jj+s)**5-jj**5 > x:
      break    
    if (jj+s)**5-jj**5 == x:
      ans = (jj+s,jj)
      chk = True
      break 
print(*ans)
### BUGGY CODE ###

X,Y,A,B,C=map(int,input().split())
p=sorted(list(map(int,input().split())))[::-1][:X]
q=sorted(list(map(int,input().split())))[::-1][:Y]
r=sorted(list(map(int,input().split())))[::-1]
pq=sorted(p+q)
for R in r:
    for i in range(len(pq)):
        if pq[i]<R:
            pq[i]=R
            break
print(sum(pq))

### FIXED CODE ###

X,Y,A,B,C=map(int,input().split())
p=sorted(list(map(int,input().split())))[::-1][:X]
q=sorted(list(map(int,input().split())))[::-1][:Y]
r=list(map(int,input().split()))
ans=sorted(p+q+r)[::-1][:X+Y]
print(sum(ans))
### BUGGY CODE ###

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        y_end = [i+1 for i in range(h-1) if (b >> i) & 1 == 1]
        count = len(y_end)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, y_end)))
        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = list(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(list(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import collections


n = int(input())
ss = []
for i in range(n):
    s = input()
    ss.append(s)
ss = sorted(ss, key=str.lower)

tmp = collections.Counter(ss).most_common()

target = collections.Counter(ss).most_common()[0][1]
ans = ''
for i in tmp:
    if i[1] == target:
        ans += i[0] + ' '
    else:
        break
ans = sorted(ans.split(), key=str.lower)
print(*ans)


### FIXED CODE ###

import bisect

n = int(input())
sl = ['']*n
for i in range(n):
    sl[i] = input()
sl = sorted(sl, key=str.lower)
# print(sl)
c = 0
anss = []
max_n = 0
for i, t in enumerate(sl):
    if i == 0:
        c += 1
        target = t
        continue

    if t == target:
        c += 1
    else:
        if max_n < c:
            anss = []
            anss.append(target)
            max_n = c
        elif max_n == c:
            anss.append(target)
            max_n = c
        target = t
        c = 1

if max_n < c:
    anss = []
    anss.append(t)
elif max_n == c:
    anss.append(t)


print(*anss)
### BUGGY CODE ###

# For taking integer inputs.
import math


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(int, input().split()))


N = inp()
a = inlist()
c = 0
while True:
    done1 = 0
    for i in range(N):
        if a[i] % 2 == 0 and done1 == 0:
            a[i] = a[i] // 2
            done1 = 1
            c += 1
        else:
            a[i] *= 3
    if done1 == 0:
        break

print(c)


### FIXED CODE ###

# For taking integer inputs.
import math


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(int, input().split()))


def getn(n):
    c = 0
    while n % 2 == 0:
        n = n // 2
        c += 1
    return c


N = inp()
a = inlist()
c = 0
for i in a:
    c += getn(i)

print(c)
### BUGGY CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**12
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import sys,resource,bisect
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(u,j,dp):
    #ddprint(f"dfs {u=} {j=}")
    ans[u] = j
    for v in dst[u]:
        if ans[v]>=0:
            continue
        x = bisect.bisect_left(dp,a[v])
        tmp = dp[x]
        dp[x] = a[v]
        #ddprint(f"dfs {u=} {j=} {x=} {tmp=} av {a[v]} {dp=}")
        dfs(v,j+(1 if tmp==BIG else 0),dp)
        dp[x] = tmp

setrlim()
n = inn()
a = inl()
a[0:0] = [0]
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v = inm()
    dst[u][v] = dst[v][u] = 1
ans = [-1]*(n+1)
dp = [BIG]*(n+1)
dp[0] = a[1]
dfs(1,1,dp)
for i in range(1,n+1):
    print(ans[i])


### FIXED CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**12
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

#import sys,resource,bisect
import resource
from sys import setrecursionlimit
from resource import getrlimit,setrlimit
from bisect import bisect_left
def setrlim():
  setrecursionlimit(250000)
  soft,hard = getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(u,j,dp):
    #ddprint(f"dfs {u=} {j=}")
    ans[u] = j
    for v in dst[u]:
        if ans[v]>=0:
            continue
        x = bisect_left(dp,a[v])
        tmp = dp[x]
        dp[x] = a[v]
        #ddprint(f"dfs {u=} {j=} {x=} {tmp=} av {a[v]} {dp=}")
        dfs(v,j+(1 if tmp==BIG else 0),dp)
        dp[x] = tmp

setrlim()
n = inn()
a = inl()
a[0:0] = [0]
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v = inm()
    dst[u][v] = dst[v][u] = 1
ans = [-1]*(n+1)
dp = [BIG]*(n+1)
dp[0] = a[1]
dfs(1,1,dp)
for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

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

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count += 1

print(count)

### FIXED CODE ###

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

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z < 0:
            break
        if z <= k:
            count += 1

print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
gates = []
for i in range(m):
	l,r = map(int,input().split())
	gates.append((l,r))
res = 0
L,R = gates[0]
if len(gates) < 2 :
	for i in range(1,n+1) :
		res += 1 if L<=i<=R else 0
	print(res)
else :
	for i in range(L,R+1) :
		flag =False
		for l,r in gates[1:] :
			if l<=i<=r :
				flag =True
			else :
				flag = False
				break
		res += 1 if flag else 0
	print(res)

### FIXED CODE ###


n,m = map(int,input().split())
L = []
R = []
for i in range(m):
	l,r = map(int,input().split())
	L.append(l)
	R.append(r)

l = L[0]
r = R[0]
cnt = 0
for i in range(max(L),min(R)+1) :
	if 0<=i<=r :
		cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]

for i in range(Q):
    A_replace = [C[i] if a == B[i] else a for a in A]
    A = A_replace
    print(sum(A))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]

sum = 0
size = 10 ** 5 + 1
list = [0] * size
for a in A:
    list[a] += 1
    sum += a

for i in range(Q):
    sum = sum + C[i] * list[B[i]] - B[i] * list[B[i]]
    list[C[i]] += list[B[i]]
    list[B[i]] = 0
    print(sum)
### BUGGY CODE ###

from collections import deque

def argmax_poss(a):
    if len(a) == 0:
        return []
    all_ = [0]
    max_ = a[0]
    for i in range(1, len(a)):
        if a[i] > max_:
            all_ = [i]
            max_ = a[i]
        elif a[i] == max_:
            all_.append(i)
    return all_

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h_poss = argmax_poss(h_scores)
max_w_poss = argmax_poss(w_scores)

out_pos_count = 0 

is_ok = False

for h in max_h_poss:
    for w in max_w_poss:
        if (h,w) not in record:
            is_ok = True
            # break
        
if is_ok:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)



### FIXED CODE ###

from collections import deque

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h = max(h_scores)
max_w = max(w_scores)
max_h_poss = [i for i,v in enumerate(h_scores) if v == max_h]
max_w_poss = [i for i,v in enumerate(w_scores) if v == max_w]

out_pos_count = 0 

c = False

for i in max_h_poss:
    for j in max_w_poss:
        if (i,j) not in record:
            c = True
            break        

if c:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []

for i in range(m):
    a.append(int(input()))

p = [0 for i in range(n)]

if 1 not in a:
    p[0] = 1

if n >= 2 and 2 not in a:
    p[1] = p[0] + 1

for i in range(2, n):
    if i + 1 not in a:
        p[i] = p[i - 1] + p[i - 2]

print(p[n - 1] % 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
a = set()

for i in range(m):
    a.add(int(input()))

p = [0 for i in range(n)]

if 1 not in a:
    p[0] = 1

if n >= 2 and 2 not in a:
    p[1] = p[0] + 1

for i in range(2, n):
    if i + 1 not in a:
        p[i] = p[i - 1] + p[i - 2]

print(p[n - 1] % 1000000007)
### BUGGY CODE ###

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

if r >= g and g >= b:
    pass
elif r >= b and b >= g:
    temp = g
    g = b
    b = temp
else:
    temp = r
    r = g
    g = temp

rg = {}
ri = 0
while ri <= n:
    gi = 0
    while gi <= n - ri:
        if (n - ri - gi) % b == 0:
            total = rg.get(ri + gi, 0)
            rg[ri + gi] = total + 1
        else:
            pass
        gi += g
    ri += r

bi = 0
result = 0

while bi <= n:
    total = rg.get(n - bi, 0)
    result += total
    bi += b

print(result)


### FIXED CODE ###

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

if r >= g and g >= b:
    pass
elif r >= b and b >= g:
    temp = g
    g = b
    b = temp
else:
    temp = r
    r = g
    g = temp

if (r == 1 and g == 1) or (r == 1 and b == 1) or (g == 1 and b == 1):
    rg = [i + 1 for i in range(n + 1)]
elif (r == 1 and g == 2) or (r == 1 and b == 2) or (g == 1 and b == 2) or (r == 2 and g == 1) or (r == 2 and b == 1) or (g == 2 and b == 1):
    rg = [1 + i // 2 for i in range(n + 1)]
else:
    rg = [0 for _ in range(n + 1)]
    ri = 0
    while ri <= n:
        gi = 0
        while gi <= n - ri:
            rg[ri + gi] += 1
            gi += g
        ri += r

bi = 0
result = 0

while bi <= n:
    total = rg[n - bi]
    result += total
    bi += b

print(result)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from copy import deepcopy
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a2 = deepcopy(a)

    for j1 in range(1, n):
        a2[j1] -= j1
    r = 0
    for i1 in range(n - 1):
        r += a2[i1+1:].count(-(a[i1]+i1))
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    l1 = []
    for ea in a:
        l1.append(cnt - ea)
        cnt += 1
    l1c = Counter(l1)
    r = 0
    for i2 in range(n):
        r += l1c[i2 + a[i2]]
    print(int(r))

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

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

def dp(cost):
    for x in range(N):
        for k in range(1,K+1):
            if x + k < N :
                tmp = abs( h[x] - h[x+k]) + cost[x]
            else:
                break
            if cost[x+k] > tmp :
                cost[x+k] = tmp


def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])

if __name__ == "__main__":
    solve()


### FIXED CODE ###

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

def dp(cost):
    for x in range(1,N):
        for k in range(max(x-K,0),x):
            cost[x] = min(cost[x] , cost[k] + abs( h[x] - h[k] ) )
        # cost[x] =  min( [ cost[k] + abs( h[x] - h[k] ) for k in range(max(x-K,0),x) ] ) 
    return 0

def solve():
    cost = [float('inf')] * N
    cost[0] = 0
    dp(cost)
    print(cost[N-1])
    return 0

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

# coding: utf-8
#Problem Name: Prime Number
#ID: tabris
#Mail: t123037@kaiyodai.ac.jp

while True:
    try:
        n = int(raw_input())
        List = []
        for i in range(1,n+1):
            List2 = []
            for j in range(2,i):
                List2.append(i % j != 0)
            if i != 1 and all(List2):
                List.append(i)
        print len(List)
    except:
        break

### FIXED CODE ###

# coding: utf-8
#Problem Name: Prime Number
#ID: tabris
#Mail: t123037@kaiyodai.ac.jp

__max = 999999
List = [False,True]*(__max/2+1)
List[1] = False
List[2] = True
for i in xrange(3,int(__max**.5)+1,2):
    List[i**2::i] = [False]*len(List[i**2::i])

List = [i for i in xrange(2,__max) if List[i]]

while True:
    try:
        n = int(raw_input())
        print __import__('bisect',fromlist=['bisect_right']).bisect_right(List,n)
    except:
        break
### BUGGY CODE ###

N = int(input())

count = 0
l = []

for i in range(1,N+1):
    a = int(str(i)[0])
    b = int(str(i)[-1])

    for i in range(1,N+1):
        x = int(str(i)[0])
        y = int(str(i)[-1])

        if a == y and b == x:
            count += 1

print(count)


### FIXED CODE ###

N = int(input())

c = [[0]*10 for i in range(10)]

for i in range(1,N+1):
    a = i % 10
    b = 0
    while i > 0:
        b = i
        i = i // 10
    c[a][b] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += c[i][j]*c[j][i]

print(ans)
### BUGGY 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()

index_list_1 = []
index_list_2 = []
count = 0

for i in b:
    index_list_1.append(len(c) - bisect.bisect_left(c, i+1))

for i in a:
    index_list_2.append(bisect.bisect_left(b, i+1))

for i in index_list_2:
    count += sum(index_list_1[i:])

print(count)

### 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()

count = 0

for i in b:
    x = bisect.bisect_left(a, i)
    y = bisect.bisect_right(c, i)
    count += x * (len(c) - y)

print(count)
### BUGGY CODE ###

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

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        if s - k <= x + y <= s:
            ans += 1

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

_, k = map(int, input().split())
h = list(map(int, input().split()))

opt = [0] * len(h)
opt[1] = abs(h[0]-h[1])

for i in range(2,len(h)):
    opt[i] = min([opt[i-j] + abs(h[i-j] - h[i]) for j in range(1,k+1) if i-j >= 0])
print(opt[len(h)-1])

### FIXED CODE ###

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

opt = [0]
for i in range(1,n):
    opt += [min([opt[-j] + abs(h[i-j] - h[i]) for j in range(1,min(i,k)+1)])]
print(opt[-1])
### BUGGY CODE ###


import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

def dist(x1, y1, x2, y2):
    return (x1-x2) ** 2 + (y1-y2) ** 2

import heapq
seen = set()
queue = [(0, dist(CH-1, CW-1, DH-1, DW-1), CH-1, CW-1)]



while queue:
    move, _, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            if (i,j) in [(-1, 0), (1, 0), (0,0), (0, -1), (0, 1)]:
                continue
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))

print(-1)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)