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

N=int(input())

for i in range(1,N+1):
    n = int(i ** 0.5)
    count=0
    for x in range(1,n+1):
        for y in range(1,n+1):
            for z in range(1,n+1):
                if x**2+y**2+z**2+x*y+y*z+x*z==i:count+=1
    print(count)

### FIXED CODE ###

N=int(input())
dic={}
for i in range(1,N+1):
    dic[i]=0
for x in range(1,int(N**0.5)):
    for y in range(1,N-x**2):
        for z in range(1,N-(x**2+y**2+x*y)):
            if x**2+y**2+z**2+x*y+x*z+y*z>N:break
            if x**2+y**2+z**2+x*y+x*z+y*z in dic:
                dic[x**2+y**2+z**2+x*y+x*z+y*z]+=1


for i in range(1,N+1):
    print(dic[i])
### BUGGY CODE ###

n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
res = [0] * n
visit = [0] * n
for i in range(1, n + 1):
    if visit[i-1]:
        continue
    link = {i}
    queue = [i]
    visit[i-1] = 1
    while queue:
        j = queue.pop(0)
        for k in friend[j]:
            if visit[k-1] == 0:
                queue.append(k)
                visit[k-1] = 1
                link.add(k)
        for i in link:
            res[i-1] = len(link)-len(link & friend[i]) - len(link & block[i]) - 1
print(*res)


### FIXED CODE ###

from collections import deque
n, m, k = map(int, input().split())
friend = [set() for _ in range(n + 1)]
block = [set() for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    a, b = map(int, input().split())
    block[a].add(b)
    block[b].add(a)
stack = deque()
ans = [0]*(n+1)
visited = [0]*(n+1)
for i in range(1, n+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in friend[n]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & friend[i]) - len(link & block[i]) -1
print(*ans[1:])
### BUGGY CODE ###

islands = []
bridges = []

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

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    b = [j for j in b if j < i['b']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))


### FIXED CODE ###

islands = []
bridges = []

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

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    # b = list(map(int, input().split()))
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)
  
  if check(b,N) != True:
    print(-1)
    
def check(B,lenB):
  # if 'get_ipython' in globals(): print(B)
  if lenB == 0 :
    return True
  #for i in reversed(range(lenB)):
  for i in range(lenB-1,-1,-1):
    if B[i] == i+1:
      if check(B[:i]+B[(i+1):],lenB -1 ) == True:
        print(B[i])
        return True
        break
  return False  

main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
### BUGGY CODE ###

import math
from functools import reduce
K = int(input())

def gcd(*numbers):
  return reduce(math.gcd, numbers)

ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
K = int(input())

def gcd(*numbers):
  return reduce(math.gcd, numbers)

ans = 0
for a in range(1,K+1):
  if (a==1):
    ans += K*K
    continue
  for b in range(1,K+1):
    t = gcd(a,b)
    if(t==1):
      ans += K
      continue
    for c in range(1,K+1):
      ans += gcd(t,c)
print(ans)
### BUGGY CODE ###

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

sum = 0
mod = 1000000000+7
for i in range(n-1):
    if a[i] >= mod:
        a[i] = a[i] % mod
    for j in range(i+1, n):
        if a[j] >= mod:
            a[j] = a[j] % mod
        sum = sum + a[i] * a[j]
        #print(sum)
        if sum >= mod:
            #print('no')
            sum = sum % mod
            #print(sum)
            #print('o')
print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
sum = 0
sum1 = 0
mod = 1000000000+7
for i in range(n):
    if a[i] >= mod:
        a[i] = a[i] % mod
    sum1 += a[i]
    sum1 %= mod
    
for i in range(n-1):
    #for j in range(i+1, n):
    sum1 -= a[i]
    #sum += a[i] * a[j]
    if sum1 < 0:
        sum1 += mod
    sum += a[i] * sum1
    sum %= mod
            
print(sum)
### BUGGY CODE ###

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')
for i in range(1,N+1):
    oya = find(i)
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1
#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()


### FIXED CODE ###

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
### BUGGY CODE ###

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

if 0 in A:
    print(0)

else:
    total = 1
    for i in range(N):
        total *= A[i]

    if total > 10**18:
        print(-1)
    else:
        print(total)


### FIXED CODE ###

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

if 0 in A:
    print(0)

else:
    total = 1
    for i in range(N):
        total *= A[i]
        if total > 10**18:
            total = -1
            break
    print(total)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
 
n=int(input())
a=sorted(list(map(int,input().split())), reverse=True)
cnt=0
for i in a:
    if a.count(i)==1:
        l=make_divisors(i)
        if len(set(a) & set(l))==1:
            cnt+=1
print(cnt)

### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))+[10**6+1]
a=sorted(a)
flag=np.array([0 for i in range(10**6+1)])
ans=0
for i in range(n):
    if flag[a[i]]==0:
        flag[::a[i]]=1
        if a[i]!=a[i+1]:
            ans+=1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
zahyo=[0]*m
for i in range(m):
    zahyo[i]=list(map(int,input().split()))
 
collec_lis=[]
for i in range(m):
    collec_lis.extend(list(range(int(zahyo[i][0]),int(zahyo[i][1])+1)))
    
import collections
c = collections.Counter(collec_lis)
 
kyotu=[int(i) for i in list(c.values()) if i==m]
print(len(kyotu))

### FIXED CODE ###


# 左右の範囲を絞っていくことで共通要素のみを炙り出す
n,m = map(int,input().split())
l = -1
r = n+1
for i in range(m):
    l_i,r_i = map(int,input().split())
    l = max(l,l_i)
    r = min(r,r_i)
print(max(0,r-l+1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = [[] for _ in range(N)]
cnt = [0 for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    cnt[p] += x

dfs(0, -1)

print(*cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

dfs(1, -1)

print(*list(cnt.values())[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np

N = int(input())

dp = np.zeros((N+1, 3), dtype=int)
arr = np.zeros((N, 3), dtype=int)
for i in range(N):
  arr[i] = list(map(int, input().split()))

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1, k] = np.maximum(dp[i+1, k], dp[i, j] + arr[i, k])
print(max(dp[N]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
dp = [[0]*3 for i in range(N+1)]
arr = [list(map(int, input().split())) for i in range(N)]

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1][k] = max(dp[i+1][k], dp[i][j] + arr[i][k])
print(max(dp[N]))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline


N = int(input())

a = list(map(int, input().split()))
A = np.array([a for i in range(N)])
B = np.array([[a[i]] * N for i in range(N)])
C = A + B
d = [i for i in range(N)]
D = np.array([d for i in range(N)])
E = np.array([[i] * N for i in range(N)])

#print(D)
#print(E)
ind = D - E
#print(ind)
ans = C - ind
#print(ans)
cnt = np.count_nonzero(ans == 0)
print(cnt)

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
B = collections.defaultdict(int)
C = collections.defaultdict(int)

for i in range(N):
    B[i-A[i]] += 1 
    C[i+A[i]] += 1
#print(B)
#print(C)
ans = 0
for i in B:
    #print(i) i=Key
    if i in C:
        ans += B[i]*C[i]
print(ans)
### BUGGY CODE ###

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

max_A = max(A)

for i in range(1, max_A + 1):
    print(A.count(i))

for i in range(max_A + 1, N+1):
    print(0)

### FIXED CODE ###

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

max_A = max(A)

from collections import Counter

dic = Counter(A)

for i in range(1, max_A + 1):
    print(dic[i])

for i in range(max_A + 1, N+1):
    print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    if h_list[i] == 0:
        costs[i] = costs[i-1]
        continue
    else:
        v = h_list[i]
    tmp = []
    start = max(0, i-k)
    for l in range(start, i):
        tmp.append(abs(v - h_list[l])+costs[l])
        if abs(v - h_list[l]) == 0:
            break
    costs[i] = min(tmp)
print(costs[-1])


### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    costs[i] = min(abs(v - h_j) + c for h_j, c in zip(h_list[start:i], costs[start:i]))
    # for l in range(start, i):
    #     tmp.append(abs(v - h_list[l])+costs[l])
    #     if abs(v - h_list[l]) == 0:
    #         break
    # costs[i] = min(tmp)
print(costs[-1])
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    box = []
    for i in range(M):
        L, R = map(int, input().split())
        box.append(L)
        box.append(R)

    # print(box)
    num = 0
    for j in range(1, N+1):
        plus = 1
        # print(j)
        if plus == 1:
            for i in range(0, len(box), 2):
                # print(box[i], box[i+1])
                if j < box[i] or box[i+1] < j:
                    plus = 0
                    break

            num += plus

    print(num)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    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)

    Lout = max(L)
    Rout = min(R)
    ans = Rout - Lout+1
    if ans < 0:
        print(0)
    else:
        print(ans)


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

import fileinput

def num_turns(total, n_1, n_2, n_3):
    with_sushi = n_1 + n_2 + n_3

    if with_sushi == 0: return 0

    res = total / (n_1 + n_2 + n_3)

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1)

    return res

inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))

### FIXED CODE ###

import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))
### BUGGY CODE ###

n=int(input())
ta=[]
t=0
a=0
ans=[[0,0]]
for i in range(n):
    p=[int(j) for j in input().split()]
    t=max(t,p[0])
    a=max(a,p[1])
    i,j=1,1
    while True:
        if p[0]*i>=t and p[1]*j>=a and p[0]*i>=ans[-1][0] and p[1]*j>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*j])
            break
        i+=1
        j+=1
 
print(sum(ans[-1]))

### FIXED CODE ###

n=int(input())
ta=[]
t=0
a=0
ans=[[1,1]]
for i in range(n):
    p=[int(j) for j in input().split()]
    i=max(ans[-1][0]//p[0],ans[-1][1]//p[1])
    while True:
        if p[0]*i>=ans[-1][0] and p[1]*i>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*i])
            break
        i+=1

print(sum(ans[-1]))
### BUGGY CODE ###

import bisect

n=int(raw_input())
x=map(int,raw_input().split())
l=int(raw_input())
q=int(raw_input())
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    cnt=0
    if a<b:
        while a!=b:
            cnt+=1
            if x[a]+l==x[bisect.bisect_left(x,x[a]+l)]:
                a=bisect.bisect_left(x,x[a]+l)
            else:
                a=bisect.bisect_left(x,x[a]+l)-1
            if a>b:
                break
    else:
        while a!=b:
            cnt+=1
            if x[a]-l==x[bisect.bisect_left(x,x[a]-l)]:
                a=bisect.bisect_left(x,x[a]-l)
            else:
                a=bisect.bisect_left(x,x[a]-l)
            if a<b:
                break
    print(cnt)



### FIXED CODE ###

import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
r=[[0]*20 for _ in xrange(n)]

for i in xrange(n):
    if x[i]+l==x[bisect.bisect_left(x,x[i]+l)]:
        r[i][0]=bisect.bisect_left(x,x[i]+l)
    else:
        r[i][0]=bisect.bisect_left(x,x[i]+l)-1

for k in xrange(19):
    for i in xrange(n):
        r[i][k+1]=r[r[i][k]][k]
        
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    ans=0
    if a>b:
        a,b=b,a
    while 1:
        if bisect.bisect_left(r[a],b)>=1:
            ans+=1<<(bisect.bisect_left(r[a],b)-1)
            a=r[a][bisect.bisect_left(r[a],b)-1]
        else :
            ans+=1<<bisect.bisect_left(r[a],b)
            break
    print(ans)
### BUGGY CODE ###

###############################################
#                                             #
#   author: raghav_0901 (Raghav Dalmia)       #
#   updated on: 04-08-2020,  3:41:14 pm IST   #
#                                             #
###############################################


from math import *

k = int(input())

if(k % 2 == 0 or k % 5 == 0):
    print(-1)
else:
    ans = 1
    num = 7
    while(ans < 100000):
        if(num % k == 0):
            print(ans)
            break
        num = (num * 10) + 7
        ans = ans + 1

### FIXED CODE ###

###############################################
#                                             #
#   author: raghav_0901 (Raghav Dalmia)       #
#   updated on: 04-08-2020,  3:48:16 pm IST   #
#                                             #
###############################################


from math import *

k = int(input())

if(k % 2 == 0 or k % 5 == 0):
    print(-1)
else:
    ans = 1
    num = 7 % k
    while(num > 0):
        num = ((num * 10) + 7) % k
        ans = ans + 1
    print(ans)
### BUGGY CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
tmp=[x for x in set(A) if A.count(x) > 1]
if len(tmp)==0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
A.sort()
for i in range(1,N):
    if A[i-1]==A[i]:
        print('NO')
        sys.exit()
print('YES')
### BUGGY CODE ###

## dijkstraで解く
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1 << 10
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heapify(q)
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while q:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw
            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] != INF:continue
            if abs(dh) + abs(dw) <= 1:
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -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())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)