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

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

n_use = dict(zip(range(1, 10), [2, 5, 5, 4, 5, 6, 3, 7, 6]))
dp = [(0, 0)]+[(0, -float('inf'))]*n # digit and produced number
# for a_j in a:
#     dp[n_use[a_j]] = (1, max(dp[n_use[a_j]][1], a_j))
for i in range(1, n+1):
    for a_j in a:
        d_cur, path_cur = dp[i]
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        else:
            d_prev, path_prev = dp[i_prev]
            path_new = a_j*pow(10, d_prev) + path_prev
            if path_new > path_cur:
                dp[i] = (d_prev+1, path_new)
            
# print(dp)
print(dp[-1][1])


### FIXED CODE ###

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

n_use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0]+[-float('inf')]*n

for i in range(1, n+1):
    for a_j in a:
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        else:
            dp[i] = max(dp[i], dp[i_prev]*10+a_j)
# print(dp)
print(dp[-1])
### BUGGY CODE ###

import numpy as np
in_list = []
for i in range(2):
    in_list.append(input())
N,S = in_list
N = int(N)

filt = []
for i in range(1,N//2+1):
    a = [0,1*i,2*i] + np.array([np.arange(N-2*i)]).T
    filt.extend(a)

res = 0
for i in filt:
    res += (S[i[0]] != S[i[1]] and S[i[1]] != S[i[2]] and S[i[2]] != S[i[0]])
    
rgb = S.count("R") * S.count("G") * S.count("B")
print(rgb - res)


### FIXED CODE ###

import numpy as np
in_list = []
for i in range(2):
    in_list.append(input())
N,S = in_list
N = int(N)

res = 0
for i in range(N-2):
    n = 1
    while True:
        j = i+n
        k = j+n
        if k > N-1: break
        res += (S[i] != S[j] and S[j] != S[k] and S[k] != S[i])
        n += 1
    
    
rgb = S.count("R") * S.count("G") * S.count("B")
print(rgb - res)
### BUGGY CODE ###

x,k,d=map(int,input().split())
if x==0:
    if d%2==0:
        print(0)
    else:
        print(d)
else:
    cou=0
    ok=True
    if x>0:
        while x>0:
            cou+=1
            x-=d
            if cou==k:
                ans=x
                ok=False
                break
        xx=x+d
        if ok:
            if cou%2==0 and k%2==0:
                ans=x
            elif cou%2==0 and k%2==1:
                ans=xx
            elif cou%2==1 and k%2==0:
                ans=xx
            else:
                ans=x
    
    if x<0:
        while x<0:
            cou+=1
            x+=d
            if cou==k:
                ans=x
                ok=False
                break
        xx=x-d
        if ok:
            if cou%2==0 and k%2==0:
                ans=x
            elif cou%2==0 and k%2==1:
                ans=xx
            elif cou%2==1 and k%2==0:
                ans=xx
            else:
                ans=x
    print(abs(ans))

### FIXED CODE ###

x,k,d=map(int,input().split())
if x==0:
    if d%2==0:
        print(0)
    else:
        print(d)
else:
    cou=0
    ok=True
    if x>0:
        xx=x
        while x>0:
            if xx-k*d>0:
                ans=x-k*d
                ok=False
                break
            cou+=1
            x-=d
            
        xx=x+d
        if ok:
            if cou%2==0 and k%2==0:
                ans=x
            elif cou%2==0 and k%2==1:
                ans=xx
            elif cou%2==1 and k%2==0:
                ans=xx
            else:
                ans=x
    
    if x<0:
        xx=x
        while x<0:
            if xx+k*d<0:
                ans=xx+k*d
                ok=False
                break
            cou+=1
            x+=d
            
        xx=x-d
        if ok:
            if cou%2==0 and k%2==0:
                ans=x
            elif cou%2==0 and k%2==1:
                ans=xx
            elif cou%2==1 and k%2==0:
                ans=xx
            else:
                ans=x
    print(abs(ans))
### BUGGY CODE ###

a,b,n=map(int,input().split())
m=0
if n<=(10**7):


    for x in range(n+1):
        l=int(a*x/b)-a*int(x/b)

        if l>=m:

            m=l

else:
    for x in range(10**6,n+1):


        l=int(a*x/b)-a*int(x/b)
        if l>m:

            m=l
print(m)


### FIXED CODE ###

a,b,n=map(int,input().split())
#0<=x<=b-1でfloor(x/b)は0となるので単調増加になる
#単調増加なのでb-1とnの小さいほうがxの最大値
x=min(b-1,n)

print(a*x//b)
### BUGGY CODE ###

import math

n, a, b = map(int, input().split())
hs = list(map(int, (input() for _ in range(n))))

m = 0
M = sum(math.ceil(h/a) for h in hs)

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)

### FIXED CODE ###

import math

n, a, b = map(int, input().split())
hs = list(map(int, (input() for _ in range(n))))

m = sum(hs) // (a + (n-1)*b) - 10
M = sum(math.ceil(h/a) for h in hs)

def killable(p, hs, a, b):
    x = sum(max(0, math.ceil((h-p*b) / (a-b))) for h in hs)
    return x <= p

while(m+1 < M):
    c = (m+M) // 2
    if killable(c, hs, a, b):
        M = c
    else:
        m = c
print(M)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[6]:


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


# In[7]:


ans = 0
for b in B:
    i = 0;j = 0
    while i<N and A[i]<b:
        i+=1
    while j<N and C[j]<=b:
        j+=1
    ans += i*(N-j)
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[8]:


from bisect import bisect_left,bisect


# In[6]:


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


# In[9]:


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


# In[ ]:
### BUGGY CODE ###

from bisect import *
n,p=map(int,input().split())
if n==1:
    print(p)
    exit()
import math 
use=math.ceil(p**(1/n))
while True :
    if p%(use**n)==0:
        print(use)
        break
    use-=1  

### FIXED CODE ###

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

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

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

n,m=map(int,input().split())
a = [int(input()) for _ in range(m)]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=(dp[i-2]+dp[i-1])%mod
print(dp[-1])


### FIXED CODE ###

n,m=map(int,input().split())
a = [int(input()) for _ in range(m)]

mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
NG=[False]*n
for i in range(m):
    NG[a[i]-1]=True

for i in range(1,n+1):
    if NG[i-1]==False:
        dp[i]=(dp[i-2]+dp[i-1])%mod
print(dp[-1])
### BUGGY CODE ###

H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

def find(A, x):
    for i, row in enumerate(A):
        if x in row:
            return row.index(x), i
    return -1, -1

for l, r in LR:
    result = 0
    x = l
    while x < r:
        y = x + D
        p1 = find(A, x)
        p2 = find(A, y)
        result += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x += D
    print(result)


### FIXED CODE ###

H, W, D = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

for l, r in LR:
    print(dt[r] - dt[l])
### BUGGY CODE ###

n,m = map(int,input().split())
lr= [list(map(int,input().split()))for a in range(m)]
ans = set(list(range(lr[0][0],lr[0][1]+1)))
for i in range(1,m):
	b = set(list(range(lr[i][0],lr[i][1]+1)))
	ans &= b
print(len(ans))


### FIXED CODE ###

n,m = map(int,input().split())
lr= [list(map(int,input().split()))for a in range(m)]
l,r = [list(b) for b in zip(*lr)]
left,right = max(l),min(r)
cnt = 0
for i in range(1,n+1):
	if left <= i and i <= right:
		cnt += 1
print(cnt)
### BUGGY CODE ###

N, K = map(int,input().split())
A = sorted(map(int,input().split()))
start = 0
end = A[-1]
l = (start + end)/2
while int(end) - start >= 0:
   l = (start + end)/2
   count = 0
   for i in range(N):
      q = A[i]/l
      if q == int(q):
         q -= 1
      count += int(q)
   if count > K:
      start = l
   else:
      end = l
ans = (start + end)/2
print(int(end) + 1)

### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
start = 0
end = 10**9
while end - start > 1:
   l = (start + end)/2
   l = int(l)
   count = 0
   for i in range(N):
      q = A[i]/l
      if q == int(q):
         q -= 1
      count += int(q)
   if count <= K:
      end = l
   else:
      start = l
print(end)
### BUGGY CODE ###

import sys
k,a,b=map(int, input().split())
if a>=b or (a<b and b-a==1):
    bis=1
    for i in range(k):
        bis+=1
    print(bis)
    sys.exit()
if a<b and (k-a+1)%2==0:
    bis=(b-a)*((k-a+1)//2-1)+b
    print(bis)
    sys.exit()
if a<b and (k-a+1)%2!=0:
    bis=(b-a)*((k-a+1)//2-1)+b+1
    print(bis)

### FIXED CODE ###

import sys
k,a,b=map(int, input().split())
if a>=b or (a<b and b-a==1):
    bis=1+k
    print(bis)
    sys.exit()
if a<b and (k-a+1)%2==0:
    bis=(b-a)*((k-a+1)//2-1)+b
    print(bis)
    sys.exit()
if a<b and (k-a+1)%2!=0:
    bis=(b-a)*((k-a+1)//2-1)+b+1
    print(bis)
### BUGGY CODE ###

import statistics
n = int(input())
a = list(map(int, input().split()))
b = []
for l in range(n):
    for r in range(l,n):
        b.append(a[(l+r+1)//2])
b.sort()
print(b[len(b)//2])


### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n = int(input())
a = list(map(int, input().split()))
def med(x):
    cum = [0] * (n+1)
    for i in range(n):
        if a[i] >= x:
            cum[i+1] = cum[i] + 1
        else:
            cum[i+1] = cum[i] - 1
    m = min(cum)
    for i in range(n+1):
        cum[i] -= m - 1
    zb = Bit(max(cum))
    ret = 0
    for j in range(n+1):
        ret += zb.sum(cum[j])
        zb.add(cum[j], 1)
    return ret
b = sorted(a)
l = 0
r = n
while(r - l > 1):
    mid = (l + r + 1) // 2
    if 2 * med(b[mid]) >= n * (n+1) // 2:
        l = mid
    else:
        r = mid
print(b[l])
### BUGGY CODE ###

N = int(input())
grundy = 0
for i in range(N):
    a, k = map(int, input().split())
    while a % k:
        a = (a - (a//k) - 1)
    grundy ^= a // k
print('Takahashi' if grundy else 'Aoki')


### FIXED CODE ###

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0
N = int(input())
grundy = 0
for i in range(N):
    a, k = map(int, input().split())
    while a % k:
        p, q = divmod(a, k)
        a -= (p + 1)*((q+p)//(p+1))

    grundy ^= a // k
print('Takahashi' if grundy else 'Aoki')
### BUGGY CODE ###

import itertools
n=int(input())
d=[]
for i in range(n):
    d.append(int(input()))
r=0
for i in range(1,n+1):
    for j in list(itertools.combinations(d,i)):
        x=sum(j)
        if r<x and x%10!=0:
            r=x
print(r)

### FIXED CODE ###

data=[]
for i in range(int(input())):
    data.append(int(input()))
un=[num for num in data if num%10==0]
data=[num for num in data if num%10!=0]
if len(data)==0:
    print(0)
else:
    if sum(un+data)%10!=0:
        print(sum(un+data))
    else:
        print(sum(un+data)-min(data))
### BUGGY CODE ###

v = input()
v = [int(x.strip()) for x in v.split(" ")]
n = v[0]
q = v[1]

p = [[0]*2]*(n-1)
for i in range(n-1):
    v=input()
    p[i] = [int(x.strip()) for x in v.split(" ")]

c = [0] * n

def func(s, y):
    c[s] += y
    for i in range(len(p)):
        if p[i][0] == s+1:
            func(p[i][1]-1,y)
    return

x = [[0]*2]*q
for i in range(q):
    v=input()
    x[i] = [int(a.strip()) for a in v.split(" ")]
    func(x[i][0]-1,x[i][1])

print(' '.join(map(str, c)))


### FIXED CODE ###

import collections

n,q = map(int, input().split())
cnt = [0] * (n+1)
g = [[] for _ in range(n+1)]

for _ in range(n-1):    #隣接リストの生成
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    v,val = map(int, input().split())
    cnt[v] += val

q = collections.deque()
q.append(1)
checked = [0]*(n+1)

while q:
    v = q.pop()
    checked[v] = 1
    for u in g[v]:
        if checked[u] == 1:
            continue
        cnt[u] += cnt[v]
        q.append(u)
print(*cnt[1:])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
tmp=[]
ans=0
for i in range (N):
	tmp.append(L[i])
	if min(tmp)==L[i]:
		ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
tmp=float("inf")
ans=0
for i in range (N):
	if tmp>L[i]:
		tmp=L[i]
		ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        n = (A[i] * A[j])%mod
        ans += n

print(ans%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
ans = 0
cs = [0]*N
cs[0] = A[0]

for i in range(1, N):
    cs[i] = cs[i-1] + A[i]

for i in range(N-1):
    n = A[i] * (cs[-1] - cs[i]) % mod
    ans += n
    ans %= mod

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

# coding: utf-8
# Your code here!
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        if S[i] != T[j]:
            total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        else:
            total[I][J] = (total[I][J-1] + total[I-1][J] + 1) % MOD
        
print((total[N][M] + 1) % MOD)

### FIXED CODE ###

# coding: utf-8
# Your code here!
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
LAST = 10**6
MOD = 10**9 + 7
S.append(LAST)
T.append(LAST)
dp = [[0 for j in range(M+2)] for i in range(N+2)]
total = [[0 for j in range(M+2)] for i in range(N+2)]
for i in range(N+1):
    for j in range(M+1):
        I,J = i+1,j+1
        total[I][J] = (total[I][J-1] + total[I-1][J] - total[I-1][J-1]) % MOD
        if S[i] != T[j]:
            continue
        
        dp[I][J] = total[I-1][J-1] + 1
        total[I][J] = (total[I][J] +  dp[I][J]) % MOD
print(dp[N+1][M+1])
### BUGGY CODE ###

def d_cake_123_binary_search(X, Y, Z, K, A, B, C):
    # editionalの解法4 O(K^2log(max(P))
    # 参考: https://atcoder.jp/contests/abc123/submissions/4871511
    import bisect
    ab = sorted([e1 + e2 for e2 in B for e1 in A])  # A, Bの要素は全部調べる
 
    # rejected 以上の値は、美味しさの合計がそれ以上である個数がK個未満である
    accepted, rejected = -1, 10**11
    while abs(accepted - rejected) > 1:
        mid = (accepted + rejected) // 2
        count = sum([len(ab) - bisect.bisect_left(ab, mid - e) for e in C])
        if count >= K:
            accepted = mid
        else:
            rejected = mid
 
    ans = []
    for e in C:
        idx = bisect.bisect_left(ab, accepted - e)
        for i in range(idx, len(ab)):
            ans.append(e + ab[i])
    ans.sort(reverse=True)
    return '\n'.join(map(str, ans[:K]))
 
X, Y, Z, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
print(d_cake_123_binary_search(X, Y, Z, K, A, B, C))

### FIXED CODE ###

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = sorted([int(i) for i in A.split()],reverse=True)[:K]
B = sorted([int(i) for i in B.split()],reverse=True)[:K]
C = sorted([int(i) for i in C.split()],reverse=True)[:K]

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

n,k=map(int,input().split())
cal=0
for i in range(1,n+1):
  for j in range(100000):
    if i*2**j<k and i*2**(j+1)>=k:
      cal+=(1/2)**(j+1)
      break
print(cal/n)

### FIXED CODE ###

n,k=map(int,input().split())
cal=0
for i in range(1,n+1):
  for j in range(1,20):
    if i>=k:
      cal+=1
      break
    elif i*2**(j-1)<k and i*2**j>=k:
      cal+=(1/2)**(j)
      break
print(cal/n)
### BUGGY CODE ###

from numba import jit
n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
    
@jit
def main():
    ans=0
    for i in range(0,n-1):
        for j in range(i+1,n):
            d=abs(data[i][0]-data[j][0])+abs(data[i][1]-data[j][1])
            ans=max(ans,d)
    print(ans)
    
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))

data_sum=[]
for i in range(n):
    data_sum.append(data[i][0]+data[i][1])


data_sum_1=[]
for i in range(n):
    data_sum_1.append(data[i][1]-data[i][0])

d_1=max(data_sum)-min(data_sum)
d_2=max(data_sum_1)-min(data_sum_1)

print(max(d_1,d_2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# C - Sum of product of pairs
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(N):
  for j in range(i + 1, N):
    ans += (A[i] * A[j]) % (10 ** 9 + 7)

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

### FIXED CODE ###

import sys
input = sys.stdin.readline

# C - Sum of product of pairs
N = int(input())
A = list(map(int, input().split()))

sum_ = sum(A)
ans = 0

for i in range(N):
  sum_ -= A[i]
  ans += A[i] * sum_
  ans %= (10 ** 9 + 7)

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

N = int(input())
S = input()

dp1 = [set() for i in range(4)]
dp2 = [set() for i in range(4)]
dp1[0].add('')
for i, S_i in enumerate(S):
    for j, dp1_j in enumerate(dp1):
        for s in dp1_j:
            dp2[j].add(s)
            if j <= 2:
                dp2[j + 1].add(s + S_i)
    dp1 = dp2
    dp2 = [set() for i in range(4)]

print(len(dp1[-1]))

### FIXED CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(1000):
    n = '{:03d}'.format(i)
    i = 0
    for d in n:
        try:
            i = S.index(d, i) + 1
        except ValueError:
            break
    else:
        cnt += 1

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

a = 0
b = 1
mid = []
ab = []

n, m = map(int, input().split())
for i in range(m):
    ab.append(list(map(int, input().split())))
    if ab[i][a] == 1:
        mid.append(ab[i][b])

# print(mid)

for _ab in ab:
    if _ab[b] == n and _ab[a] in mid:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

A = 0
B = 1
mid = [0] * (n+1)
goal = [0] * (n+1)
ab = []

for i in range(m):
    a,b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        mid[b] += 1
    elif b == n:
        goal[a] += 1

# print(mid)
# print(goal)

for i in range(n+1):
    if mid[i] == 1 and goal[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

s=str(input())
se=[s]
n=len(s)
num=0
total=n*(n-1)//2+1
s_="0"+s
for i in range(n):
  for j in range(1,n-i):
    k=s_[1:i+1]+s_[i+j+1:i:-1]+s_[i+j+2:]
    if k in se: num-=1
    else: se+=[k]
print(num+total)

### FIXED CODE ###

s=str(input())
L=[0]*26
n=len(s)
for i in range(n):
  L[ord(s[i])-97]+=1
num=0
total=n*(n-1)//2 +1
for i in range(26):
  if L[i]>1:
    num+=L[i]*(L[i]-1)//2
print(total-num)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
heap = [(0, Ch, Cw)]
while heap:
    d, i, j = heappop(heap)
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            heappush(heap, (d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                heappush(heap, (d + 1, ni, nj))
print(-1)



### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)