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

N = int(input())
p = list(map(float,input().split()))

dp = [[0]*(N+1) for i in range(N)]

dp[0][0] = 1-p[0]
dp[0][1] = p[0]

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

### FIXED CODE ###

N = int(input())
p = list(map(float,input().split()))

dp = [[0]*(N+1) for i in range(N)]

dp[0][0] = 1-p[0]
dp[0][1] = p[0]

for i in range(1,N):
    dp[i][0] = (1-p[i])*dp[i-1][0]
    for j in range(1,i+2):
        dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1-p[i])
        
print(sum(dp[-1][(N+1)//2:]))
### BUGGY CODE ###

n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
w_tot=sum(W)
DP=[[-float("inf") for i in range(w_tot+1)] for j in range(n)]
for i in range(n):
  DP[i][0]=0
DP[0][W[0]]=V[0]
for i in range(1,n):
  for j in range(w_tot+1):
    if j>=W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(max(DP[n-1][i] for i in range(w_max+1)))

### FIXED CODE ###

n,w_max=map(int,input().split())
W,V=[],[]
for i in range(n):
  w,v=map(int,input().split())
  W.append(w)
  V.append(v)
DP=[[0 for i in range(w_max+1)] for j in range(n)]
for i in range(w_max+1):
  if i>=W[0]:
    DP[0][i]=V[0]
for i in range(1,n):
  for j in range(w_max+1):
    if j>W[i]:
      DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+V[i])
    elif j==W[i]:
      DP[i][j]=max(DP[i-1][j],V[i])
    else:
      DP[i][j]=DP[i-1][j]
print(DP[n-1][w_max])
### BUGGY CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]

ans = 10 ** 20

for i in range(n):
    for j in range(i+1, n):
        for ii in range(n):
            for jj in range(ii+1, n):
                l = min(xy[i][0], xy[j][0])
                r = max(xy[i][0], xy[j][0])
                d = min(xy[ii][1], xy[jj][1])
                u = max(xy[ii][1], xy[jj][1])
                cnt = 0
                for x,y in xy:
                    if l <= x <= r and d <= y <= u:
                        cnt += 1
                if cnt >= k:
                    ans = min(ans, (r-l) * (u - d))

print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]

xy.sort()
ans = 10**20

for i in range(n):
    for j in range(i,n):
        xy_tmp = xy[i:j+1]
        if len(xy_tmp) >= k:
            l1 = xy_tmp[0][0]
            r1 = xy_tmp[-1][0]
            xy_tmp.sort(key = lambda x: x[1])
            for jj in range(len(xy_tmp) - k + 1):
                ans = min(ans, (r1-l1) * (xy_tmp[k+jj-1][1] - xy_tmp[jj][1]))

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

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

total = 0
for i in range(N):
    a = nums[i]
    for j in range(i+1, N):
        total += a * nums[j]

print(total % (1000000007))

### FIXED CODE ###

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

total = 0
sums = []
tmp = 0

for i in range(1, N):
    tmp += nums[N-i]
    sums.append(tmp)

for i in range(N-1):
    a = nums[i]
    b = sums[N-(i+2)]
    total += a*sums[N-(i+2)]

print(total % (1000000000+7))
### BUGGY CODE ###

n = int(input())
ans = 0
for j in range(10):
    for k in range(10):
        cnt1 = 0
        cnt2 = 0
        for i in range(1,n+1):
            s = str(i)
            if s[0] == str(k)and s[-1] == str(j):
                cnt1 += 1
            if s[0] == str(j) and s[-1] == str(k):
                cnt2 += 1
        ans += cnt1*cnt2
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
tbl1 = [[0]*10 for i in range(10)]
tbl2 = [[0]*10 for i in range(10)]
# for j in range(10):
#     for k in range(10):
#         cnt1 = 0
#         cnt2 = 0
#         for i in range(1,n+1):
#             s = str(i)
#             if s[0] == str(k)and s[-1] == str(j):
#                 cnt1 += 1
#             if s[0] == str(j) and s[-1] == str(k):
#                 cnt2 += 1
#         ans += cnt1*cnt2
for i in  range(1,n+1):
    s = str(i)
    for j in range(10):
        for k in range(10):
            if s[0] == str(k)and s[-1] == str(j):
                tbl1[k][j] += 1
            if s[0] == str(j) and s[-1] == str(k):
                tbl2[j][k] += 1
for j in range(10):
        for k in range(10):
            ans += tbl1[k][j] * tbl2[j][k]
print(ans)
### BUGGY CODE ###

sum=0
while 1:
 x=raw_input
 sum+=1
 if x == '0':
    break
 print 'Case %s: %s' %(sum, x)

 

### FIXED CODE ###

sum = 0
while 1:
   x = int(raw_input())
   sum = sum + 1
   if x == 0:
      break
   print 'Case %s: %s' %(sum, x)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
num = 0
ans = 0
for i in range(N-K+1):
    for j in range(K):
        ans += p[i+j]
    ans += K
    ans /= 2
    
    if num < ans:
        num = ans
    ans = 0    
print(num)

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
for i in range(N):
  P[i]=(P[i]+1)/2
point=sum(P[:K])
tmp=point
for i in range(N-K):
  tmp=tmp-P[i]+P[i+K]
  if tmp>point:point=tmp
  
print(point)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
zf = 0
for i in range(n):
    if a[i] == 0:
        ans = 0
    ans = ans * a[i]
    if ans > 1000000000000000000:
        ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n):
    if a[i] == 0:
        ans = 0
    if ans != -1:
        ans = ans * a[i]
    if ans > 1000000000000000000:
        ans = -1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
s = []
r = []
for i in range(m):
    s.append(list(map(int,input().split())))
for i in range(m):
    rank = 1
    for j in range(m):
        if s[i][0] == s[j][0] and s[i][1] > s[j][1]:
            rank += 1
    prefString = str(s[i][0])
    rankString = str(rank)
    Number1st = "0" * (6-len(prefString)) + prefString 
    Number2nd = "0" * (6-len(rankString)) + rankString
    print(Number1st+Number2nd)

### FIXED CODE ###

n,m=map(int,input().split())
s = []
for i in range(m):
    pref,year=map(int,input().split())
    s.append([pref,year,i])
s.sort()
rank = 1
for i in range(m):
    if s[i][0] != s[i-1][0]:
        rank = 1
    s[i][1]=rank
    rank += 1
s.sort(key=lambda x: x[2]) 
for i in range(m):
    print("0"*(6-len(str(s[i][0])))+str(s[i][0])+"0"*(6-len(str(s[i][1])))+str(s[i][1]))
### BUGGY CODE ###

#coding: utf-8
N = int(input())
A= list(map(int,input().split()))
A = [0] + A + [0]
Adiff = list(range(N+1))
def diff(X):
    diff_x = 0
    for i in range(len(X)-1):
        diff_x += abs(X[i] - X[i+1])
    return diff_x
for i in range(N):
    B = A[:]
    del B[i+1]
    diffB = diff(B)
    print(diffB)


### FIXED CODE ###

#coding: utf-8
N = int(input())
A= list(map(int,input().split()))
A = [0] + A + [0]
def diff(X):
    diff_x = list(range(len(X)-1))
    for i in range(len(X)-1):
        diff_x[i] = abs(X[i] - X[i+1])
    return diff_x
Adiff = diff(A)
SUM = 0
for i in range(len(Adiff)):
    SUM += Adiff[i]
for i in range(N):
    SUMM = SUM
    SUMM += abs(A[i]-A[i+2]) - Adiff[i+1]-Adiff[i]
    print(SUMM)
### BUGGY CODE ###

N, C = map(int, input().split())
d = []
for i in range(C):
    tmp = [int(x) for x in input().split()]
    d.append(tmp)

c = []
for i in range(N):
    tmp = [int(x)-1 for x in input().split()]
    c.append(tmp)

x = [[], [], []] # 0,1,2
for cc in range(C):
    tx = [0] * 3
    for i in range(N):
        for j in range(N):
            tx[(i+j)%3] += d[c[i][j]][cc]
    for i in range(3):
        x[i].append(tx[i])

ans = 10 ** 9
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or k == i:
                continue
            tmp = x[0][i] + x[1][j] + x[2][k]
            if tmp < ans:
                ans = tmp
print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
d = []
for i in range(C):
    tmp = [int(x) for x in input().split()]
    d.append(tmp)

c = []
for i in range(N):
    tmp = [int(x)-1 for x in input().split()]
    c.append(tmp)

x = [[], [], []] # 0,1,2
for cc in range(C):
    tx = [0] * 3
    for i in range(N):
        for j in range(N):
            tx[(i+j)%3] += d[c[i][j]][cc]
    for i in range(3):
        x[i].append(tx[i])

ans = 10 ** 9
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or k == i:
                continue
            tmp = x[0][i] + x[1][j] + x[2][k]
            if tmp < ans:
                ans = tmp
print(ans)
### BUGGY CODE ###

S = len(input())
cnt = "x"
length = 0
a = "x"
while S != length:
    cnt = cnt + a
    length = len(cnt)
print(cnt)


### FIXED CODE ###

S = len(input())
cnt = ""
length = 0
a = "x"
for i in range(S):
    cnt = cnt + a
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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


def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        ok = True
        dp = {}
        needreset = 10**15
        # これより長かったらdpにあろうがなかろうが存在しないものになる
        exception = set()
        pre = -1
        for a in A:
            ind = a
            for _ in range(100):
                # 修正
                if needreset >= ind or ind in exception:
                    if not ind in dp.keys():
                        dp[ind] = 0 if pre < a else 1
                else:
                    dp[ind] = 0 if pre < a else 1
                    exception.add(ind)
                # たす
                if dp[ind] < m:
                    dp[ind] += 1
                    break
                elif ind == 1:
                    ok = False
                    break
                else:
                    # 繰り上がり
                    dp[ind] = 1
                    ind -= 1
            if not ok: break
            # 更新
            if pre > a:
                needreset = a
                exception = set()
            pre = a

        if ok:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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


def check(m):
    if m == 1:
        pre = -1
        for a in A:
            if pre >= a:
                return False
            pre = a
    else:
        dp = {}
        pre = 0
        #count = 0
        for a in A:
            if pre < a:
                pre = a
                continue
            todelete = []
            for b in dp.keys():
                if b > a:
                    todelete.append(b)
            ind = a
            while ind > 0:
                if ind in dp and dp[ind] >= m-1:
                    todelete.append(ind)
                else:
                    break
                ind -= 1
            # 更新
            if ind in dp:
                dp[ind] += 1
            else:
                dp[ind] = 1
            if ind == 0 or dp[ind] >= m:
                return False
            for d in todelete:
                del dp[d]
            pre = a
    #print(m, count)
    return True



def main():
    l = 0
    r = N
    while r-l > 1:
        m = (r+l)//2
        if check(m):
            r = m
        else:
            l = m
    print(r)


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

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [{0} for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    seen = [False]*N
    K = 0
    used = {0}

    def dfs(v):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (G_c[u] | G_c[next_v]) ^ used:
                    c = max((G_c[u] | G_c[next_v]) ^ used)
                else:
                    c = max(G_c[u] | G_c[next_v]) + 1
                    used.add(c)
                # print(u, next_v, G_c[u] | G_c[next_v], c)
                seen[next_v] = True
                colors[u, next_v] = c
                colors[next_v, u] = c
                G_c[u].add(c)
                G_c[next_v].add(c)
                todo.append(next_v)
                break
            else:
                todo.pop()
    dfs(0)
    # print(G_c)
    print(max(len(c) - 1 for c in G_c))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

S=input()
s=int(S)
c=0
for i in range(1,s//2019+1):
  C=str(2019*i)
  if '0' in C:
    continue
  if C in S:
    c+=1
print(c)


exit()




c=0;s=[]
for i in range(0,len(S)+1):
  for j in range(i,len(S)):
    s.append(S[i:j+1])
del s[0]
ss = [int(i) for i in s]    
#print(ss)
sss = list(map(lambda x: x %2019, ss))

#print(sss)
print(sss.count(0))


### FIXED CODE ###

S=input()
s=int(S)
mod=2019
c=[0]*(len(S)+1)
d=[0]*2019


c[0]=0
d[0]=1
for i in range(len(S)):
  c[i+1]=(c[i]+int(S[-i-1])*pow(10,i,mod))%mod
  d[c[i+1]]+=1
  
m=0
for i in range(2019):
  m+=d[i]*(d[i]-1)//2

print(m)
### BUGGY CODE ###

a,b,k= map(int, input().split())
x = sorted(list(i for i in range(a, b+1)))
y = sorted(list(set(x[:k]+x[-k:])))
for i in y:
    print(i)

### FIXED CODE ###

a,b,k= map(int, input().split())
c = min(k, b-a+1)
x = [a+i for i in range(c)]
y = [b-i for i in range(c)]
z = sorted(list(set(x+y)))
for i in z:
    print(i)
### BUGGY CODE ###

import copy
import collections

def Neighbohood(V,E,v):
    H=[]
    for w in V:
        if ((v,w) in E) or ((w,v) in E):
            H.append(w)

    return H

def bfs(V,E):
    W=[ v for v in V]
    Q=collections.deque([W[0]])
    searched = { v: False for v in W}
    searched[W[0]] = True
    L={v:None for v in W}
    n=1
    
    while len(Q) != 0:
        v=Q.popleft()
        Nei=Neighbohood(V,E,v)

        D=[x for x in Nei if searched[x]==False]
        
        for w in D:
            Q.append(w)
            L[w]=v
            searched[w] = True
            n+=1
            
    return (L,n)

#メイン部
N,M=map(int,input().split())

V=list(range(1,N+1))

E=[]
for i in range(M):
    v,w=map(int,input().split())
    E.append((v,w))

(L,n)=bfs(V,E)
if N==n:
    print("Yes")
    for i in range(2,N+1):
        print(L[i])
else:
    print("No")


### FIXED CODE ###

import copy
import collections

#メイン部
N,M=map(int,input().split())

V=list(range(1,N+1))
H={v:set() for v in V}
L={v:None for v in V}

for i in range(M):
    v,w=map(int,input().split())
    H[v].add(w)
    H[w].add(v)

Q=collections.deque()
Q.append(V[0])

L[1]=1
n=1

while Q:
    x=Q.popleft()
    for v in H[x]:
        if L[v]!=None:
            continue
        L[v]=x
        n+=1
        Q.append(v)

if n==N:
    print("Yes")
    for i in range(2,N+1):
        print(L[i])
else:
    print("No")
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

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

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

R, C, K = mapint()
dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
from collections import defaultdict
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

for r in range(R):
    for c in range(C):
        v = dic[r][c]
        for i in range(4):
            if c!=0:
                dp[r][c][i] = dp[r][c-1][i]
            if r!=0:
                dp[r][c][0] = max(dp[r][c][0], dp[r-1][c][i])
        for i in range(2, -1, -1):
            dp[r][c][i+1] = max(dp[r][c][i+1], dp[r][c][i]+v)

print(max(dp[R-1][C-1]))

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

R, C, K = mapint()
last_dp = [[0]*4 for _ in range(C)]
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

for r in range(R):
    dp = [[0]*4 for _ in range(C)]
    for c in range(C):
        v = dic[r][c]
        for i in range(4):
            if c!=0:
                dp[c][i] = dp[c-1][i]
            if r!=0:
                dp[c][0] = max(dp[c][0], last_dp[c][i])
        if v!=0:
            for i in range(2, -1, -1):
                dp[c][i+1] = max(dp[c][i+1], dp[c][i]+v)
    last_dp = dp

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

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))

dict = {}
for i in range(N):
  if A[i] in dict.keys():
    dict[A[i]] += 1
  else:
    dict[A[i]] = 1

fact = []

fact.append(1)
for i in range(1, N+1):
  fact.append(fact[i-1] * i)

def comb(n,k):
  if n<k:
    return 0
  return int(fact[n] / fact[k] / fact[n-k])

# all
ret = 0
for key in dict.keys():
  val = dict[key]
  ret += comb(val, 2)

# i >= 0
for i in range(N):
  val_n = dict[A[i]]
  next_ret = ret - comb(val_n, 2) + comb(val_n - 1, 2)
  print(next_ret)

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = list(map(int, input().split()))

dict = {}
for i in range(N):
  if A[i] in dict.keys():
    dict[A[i]] += 1
  else:
    dict[A[i]] = 1

def comb(n):
  if n<2:
    return 0
  return int(n * (n - 1) / 2)

# all
ret = 0
for key in dict.keys():
  val = dict[key]
  ret += comb(val)

# i >= 0
for i in range(N):
  val_n = dict[A[i]]
  next_ret = ret - comb(val_n) + comb(val_n - 1)
  print(next_ret)
### BUGGY CODE ###

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

S = [0 for _ in range(N+1)]
mod = 1000000007

for i in range(N-1):
    st = 0
    for j in range(i+1):
        st += A[j] * A[i+1]
    S[i+1] = S[i] + st

print(int(S[N-1] % mod))

### FIXED CODE ###

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

S = [0 for _ in range(N+1)]
T = [0 for _ in range(N+1)]
mod = 1000000007

for i in range(N-1):
    st = 0
    T[i+1] = T[i] + A[i]
    S[i+1] = S[i] + A[i+1] * T[i+1]

print(int(S[N-1] % mod))
### BUGGY CODE ###

import heapq as q

n, k = map(int, input().split())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l += [a]*b
q.heapify(l)
for i in range(k):
    ans = q.heappop(l)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
l = [0]*(10**5+10)

for i in range(n):
    a, b = map(int, input().split())
    l[a] += b

sum = 0
for i in range(len(l)):
    sum += l[i]
    if sum >= k:
        print(i)
        break
### BUGGY CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.appendleft((nx, ny, c+1, d, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)

### FIXED CODE ###

import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)