Harryxun/stf_run huggingface dataset:
def LCS():
  x = ' ' + raw_input()
  y = ' ' + raw_input()
  X = len(x)
  Y = len(y)
  
  for i in range(X):
    c[i][0] = 0
  for j in range(Y):
    c[0][j] = 0


  for i in range(X):
    for j in range(Y):
      if X[i] == Y[i]: 
        c[i][j] = c[i - 1][j - 1] + 1
      elif c[i - 1][j] >= c[i][j - 1]:
        c[i][j] = c[i - 1][j]
      else:
        c[i][j] = c[i][j - 1]
  print c[X][Y]


q = input()


for i in range(q):
  LCS()

### FIXED CODE ###

def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()
from collections import deque

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

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

start = -1
for v in range(n):
    if len(g[v]) == 0:
        continue
    start = v
    break

memo = [0] * n
memo[start] = 1
count = 0
q1 = deque([])
q2 = deque([])
for v in g[start]:
    if memo[v] == 1:
        continue
    memo[v] = 1
    count += 1
    if count > 2:
        break
    if count == 1:
        q1.append(v)
    elif count == 2:
        q2.append(v)

ans1 = [start]
while q1:
    node = q1.popleft()
    ans1.append(node)
    flag = 0
    for nv in g[node]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q1.append(nv)
        flag = 1
        break
    if flag == 0:
        break

ans2 = []
while q2:
    node = q2.popleft()
    ans2.append(node)
    flag = 0
    for nv in g[node]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q1.append(nv)
        flag = 1
        break
    if flag == 0:
        break

ans1 = ans1[::-1]


ans = []
for i in ans1:
    ans.append(i+1)
for i in ans2:
    ans.append(i+1)
print(len(ans))
print(*ans)


### FIXED CODE ###

from collections import deque

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

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

start = -1
for v in range(n):
    if len(g[v]) == 0:
        continue
    start = v
    break

memo = [0] * n
memo[start] = 1
count = 0
q1 = deque([])
q2 = deque([])
for v in g[start]:
    if memo[v] == 1:
        continue
    count += 1
    if count > 2:
        break
    memo[v] = 1
    if count == 1:
        q1.append(v)
    elif count == 2:
        q2.append(v)

ans1 = [start]
while q1:
    node = q1.popleft()
    ans1.append(node)
    flag = 0
    for nv in g[node]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q1.append(nv)
        flag = 1
        break
    if flag == 0:
        break

ans2 = []
while q2:
    node = q2.popleft()
    ans2.append(node)
    flag = 0
    for nv in g[node]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q2.append(nv)
        flag = 1
        break
    if flag == 0:
        break

ans1 = ans1[::-1]


ans = []
for i in ans1:
    ans.append(i+1)
for i in ans2:
    ans.append(i+1)
print(len(ans))
print(*ans)
LL = [int(i) for i in input().split()]
H = LL[0]
W = LL[1]
A = LL[2]
B = LL[3]

Math = [[0 for a in range(W)] for b in range(H)] 

for i in range(A):
    for j in range(B):
        Math[i][j] = 1

for i in range(W - A):
    for j in range(H - B):
        Math[H - i][W -j] = 1

for i in range(H):
    print(*Math) 

### FIXED CODE ###

h, w, a, b = map(int, input().split())
for i in range(b):
    for j in range(a):
        print(0, end='')
    for j in range(w - a):
        print(1, end='')
    print()
for i in range(h - b):
    for j in range(a):
        print(1, end='')
    for j in range(w - a):
        print(0, end='')
    print()
n, t = list(map(int,input().split()))
list1 = []
list2 = []
for i in range(0,int(n)):
  list1.append(list(map(int, input().split())))

for i in list1:
  if int(i[1]) <= int(t):
    list2.append(i)

list2.sort()
print(list2[0][0])

### FIXED CODE ###

n, t = list(map(int,input().split()))
list1 = []
list2 = []
for i in range(0,n):
  list1.append(list(map(int, input().split())))

for i in list1:
  if int(i[1]) <= t:
    list2.append(i)

if(list2):
  list2.sort()
  print(list2[0][0])
else:
  print("TLE")
N = int(input())
H = list(map(int,input().split()))
sum = 1
result = 0
if H[0] <= H[1]:
    result = H[1]
else:
    result = H[0]
for i in range(1,len(H)):
    if H[i-1] <= H[i] and result <= H[i]:
        sum += 1

print(sum)


### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
count,ans = 0,0
for i in H:
    if count <= i:
        count = i
        ans = ans + 1
print(ans)
print(str(int(input())^^3))

### FIXED CODE ###

N = int(input())
print(str(N ** 3))
W = input()

count = 0
while True:
    line = input()
    if line == 'END_OF_TEXT'
        break
        
    for s in line.split():
        if s == W:
            count += 1
        
print(count)

### FIXED CODE ###

W = input().lower()

count = 0
while True:
    line = input()
    if line == 'END_OF_TEXT':
        break

    for s in line.lower().split():
        if s == W:
            count += 1

print(count)
#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if i+1>=N:
            break
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
            ans=(ans*A2n[ni])%MOD
            K-=2
            ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
input=sys.stdin.readline
MOD=10**9+7


def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    if N==1:
        print(A[0])
        exit()
    A.sort()
    A2n=[]
    for i in range(0,N,2):
        if i+1>=N:
            break
        if A[i]<=0 and A[i+1]<=0:
            A2n.append(A[i]*A[i+1])
        else:
            break

    A.sort(reverse=True)
    ans=1
    if A[0]<=0 and K%2==1:
        for i in range(K):
            ans=(ans*A[i])%MOD
        print(ans)
        exit()
    ni=0
    i=0
    while(K>0):
        if i+1<N and len(A2n)-ni>0 and A[i]*A[i+1]<A2n[ni] and K>=2:
                ans=(ans*A2n[ni])%MOD
                K-=2
                ni+=1
        else:
            ans=(ans*A[i])%MOD
            i+=1
            K-=1
    print(ans)
            
    
    
if __name__=="__main__":
    main()
import math
k, m = map(int, input().split())
x = math.ceil((k-1)/(n-1))

print(x)

### FIXED CODE ###

import math
k, m = map(int, input().split())
x = math.ceil((k-1)/(m-1))
 
print(x)
import numpy as np
import scipy.special as ss
N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)
v = np.array(v)
##print(v)
ansarray = v[0:A]
##print(ansarray)
ave = np.mean(ansarray)
print(float(ave))
mi = min(ansarray)
ma = max(ansarray)
biggerarray = v[v>mi]
m = len(biggerarray)
numminarray = v[v==mi]
a = len(numminarray)
##print(nummin)
##print(num_kouho)
ans = 0
if ma == mi:
    if m+a <= B:
        for i in range(A-m,a+1):
            ans+=ss.comb(a,i)
    else:
        for i in range(A-m,B-m+1):
            ans+=ss.comb(a,i)

else:
    ans = a
#print('a=',a)
#print('m=',m)
print(int(ans))
    


### FIXED CODE ###

import numpy as np
import math
def ncm(n,m):
    return math.factorial(n)/(math.factorial(m) * math.factorial(n-m))

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)
v = np.array(v)
##print(v)
ansarray = v[0:A]
##print(ansarray)
ave = np.mean(ansarray)
print(float(ave))
mi = min(ansarray)
ma = max(ansarray)
biggerarray = v[v>mi]
m = len(biggerarray)
numminarray = v[v==mi]
a = len(numminarray)
##print(nummin)
##print(num_kouho)
ans = 0
if ma == mi:
    if m+a <= B:
        for i in range(A-m,a+1):
            ans+=ncm(a,i)
    else:
        for i in range(A-m,B-m+1):
            ans+=ncm(a,i)

else:
    ans = ncm(a,A-m)
#print('a=',a)
#print('m=',m)
print(int(ans))
a,b,c=map(int,input().split())
s=abs(a-b)+abs(b-c)+abs(c-a)
mn=max(abs(a-b)+abs(b-c)+abs(c-a))
print(s-mn)

### FIXED CODE ###

a,b,c=map(int,input().split())
s=abs(a-b)+abs(b-c)+abs(c-a)
m=max(abs(a-b),abs(b-c),abs(c-a))
print(s-m)
import sys
x, n = map(int, input().split())
if n == 0:
    print(x)
    exit(1)
p = [int(x) for x in input().split()]
k = 0
while x in p:
    if not x - k in p:
        print(x - k)
        exit(1)
    elif not x + k in p:
        print(x + k)
        exit(1)
    else:
        k += 1
        continue
print(x)

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = [int(x) for x in input().split()]
    for i in range(n + 1):
        if not x - i in p:
            print(x - i)
            break
        elif not x + i in p:
            print(x + i)
            break
        else:
            continue
n = int(input())
s = list(input())
type = "A"
count = 0
for char in s:
    if char == "A"
        type = "B"
    elif char == "B" and type == "B":
        type = "C"
    elif char == "C" and type == "C":
        count += 1
        type = "A"
    else:
        type = "A"
print(count)

### FIXED CODE ###

n = int(input())
s = list(input())
type = "A"
count = 0
for char in s:
    if char == "A":
        type = "B"
    elif char == "B" and type == "B":
        type = "C"
    elif char == "C" and type == "C":
        count += 1
        type = "A"
    else:
        type = "A"
print(count)
A,B=map(int,input(),split())
if A,B<=9:
  print(A*B)
else:
  print(-1)

### FIXED CODE ###

A,B=map(int,input().split())
if A<=9 and B<=9:
  print(A*B)
else:
  print(-1)
n1, n2, n3 = list(map(int, input().split()))
print((n1-n2)*(n1-n3))

### FIXED CODE ###

n1=int(input())
n2=int(input())
n3=int(input())
out=(n1-n2+1)*(n1-n3+1)
print(out)
import numpy as np

N, M = map(int, input().split())
H = np.array(list(map(int, input().split())))

streetMatrix = np.array([np.zeros(N)]*N)

for m in range(M):
    A, B = map(int, input().split())
    
    streetMatrix[A-1][B-1] = 1
    streetMatrix[B-1][A-1] = 1

countGood = 0

for i in range(N):
    if max(streetMatrix[i]) == 0:
        countGood += 1
    elif H[i] > max(streetMatrix[i] * H):
        countGood += 1
print(countGood)

### FIXED CODE ###

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

competitor_H = {}

for m in range(M):
    A, B = map(int, input().split())
    
    if A-1 not in competitor_H.keys():
        competitor_H[A-1] = []
    competitor_H[A-1].append(H[B-1])
    
    if B-1 not in competitor_H.keys():
        competitor_H[B-1] = []
    competitor_H[B-1].append(H[A-1])

countGood = 0
for i in range(N):
    if i not in competitor_H.keys():
        countGood += 1
    elif H[i] > max(competitor_H[i]):
        countGood += 1
print(countGood)
import numpy as np
import sys
sys.setrecursionlimit(100000)

def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    total = np.array([0]*m)
    global ans
    ans = 10**7
    for i in range(n):
        c, *a = map(int, input().split())
        a = np.array(a)
        cl[i] = c
        al[i] = a
        total += a
    def dfs(i, cost, A):
        i += 1
        if i == n:
            global ans
            if all([ai >= x for ai in A]) and ans > cost:
                ans = cost
            return
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(100000)

def main():
    n, m, x = map(int, input().split())
    cl = [None]*n
    al = [None]*n
    total = np.array([0]*m)
    global ans
    ans = 10**7
    for i in range(n):
        c, *a = map(int, input().split())
        a = np.array(a)
        cl[i] = c
        al[i] = a
        total += a
    def dfs(i, cost, A):
        i += 1
        if i == n:
            global ans
            if all([ai >= x for ai in A]) and ans > cost:
                ans = cost
            return
        dfs(i, cost, A[:])
        dfs(i, cost+cl[i], A[:]+al[i])
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**7:
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()
# coding: utf-8
import sys
import numpy as np
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
V = np.array(lr(), np.float64)
V.sort()
V = np.flip(V)
Vcum = V.cumsum()
ave = Vcum / np.arange(1, N+1)
ma = ave[A-1:B].max()
print(ma)
cases = 0
Vrev = np.flip(V)
for i, x in enumerate(ave[A-1:B], A-1):
    if x != ma:
        continue
    j = np.searchsorted(Vrev, V[i])
    k = np.searchsorted(Vrev, V[i], side='right')
    if j+1 == k:
        cases += 1
        continue
    r = i+1-j
    n = k-j
    a = factorial(n) / factorial(r) / factorial(n - r)
    cases += a

print(int(cases))


### FIXED CODE ###

import sys
import numpy as np
from math import factorial

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B = lr()
V = np.array(lr())
V.sort()
if A == 1:
    ave = V[-A]
else:
    ave = V[-A:].sum() / A
print(ave)
left_i = np.searchsorted(V, V[-A], side='left')
right_i = np.searchsorted(V, V[-A], side='right')
num = right_i - left_i
done = N - right_i

bottom = A-done
top = B-done

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

answer = combinations_count(num, bottom)
if ave == V[-A] and num > 1:
    for i in range(bottom+1, min(num, top)+1):
        answer += combinations_count(num, i)

print(answer)
# 15
a=int(input())
b=int(input())
c=int(input())
if a==b and b==c and a==c: #全部一緒のとき
    print("1")
elif a!=b and b!=c and a!=c: #全部違うとき
    print("3")
elif a==b and b!=c:
    print("2")
elif a==c and c!=b:
    print("2")
elif c==b and a!=c:
    print("2")

### FIXED CODE ###

a,b,c=map(int,input().split())
if a==b and b==c and a==c: #全部一緒のとき
    print("1")
elif a!=b and b!=c and a!=c: #全部違うとき
    print("3")
elif a==b and b!=c:
    print("2")
elif a==c and c!=b:
    print("2")
elif c==b and a!=c:
    print("2")
H, W, K = map(int, input().split())
c = []
cnt = [0] * W
num = 0
A = [[0] * W for _ in range(H)]

for i in range(H):
    row = list(input())
    c.append(row)
    cnt[i] = row.count("#")


def solve(cl, cr):
    global num
    P = []
    for i in range(cl, cr + 1):
        for j in range(W):
            if c[i][j] == "#":
                P.append(j)
    P = sorted(P)
    for i in range(len(P)):
        v1 = 0
        v2 = W - 1
        if (i >= 1):
            v1 = P[i - 1] + 1
        if (i < len(P) - 1):
            v2 = P[i]
        num += 1
        for j in range(cl, cr + 1):
            for k in range(v1, v2 + 1):
                A[j][k] = num


vec = []
for i in range(H):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1 = 0
    v2 = H - 1
    if (i >= 1):
        v1 = vec[i - 1] + 1
    if (i < len(vec) - 1):
        v2 = vec[i]
    solve(v1, v2)
for i in range(H):
    print(*A[i])


### FIXED CODE ###

H, W, K = map(int, input().split())
c = []
cnt = [0] * H
num = 0
A = [[0] * W for _ in range(H)]

for i in range(H):
    row = list(input())
    c.append(row)
    cnt[i] = row.count("#")


def solve(cl, cr):
    global num
    P = []
    for i in range(cl, cr + 1):
        for j in range(W):
            if c[i][j] == "#":
                P.append(j)
    P = sorted(P)
    for i in range(len(P)):
        v1 = 0
        v2 = W - 1
        if (i >= 1):
            v1 = P[i - 1] + 1
        if (i < len(P) - 1):
            v2 = P[i]
        num += 1
        for j in range(cl, cr + 1):
            for k in range(v1, v2 + 1):
                A[j][k] = num


vec = []
for i in range(H):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1 = 0
    v2 = H - 1
    if (i >= 1):
        v1 = vec[i - 1] + 1
    if (i < len(vec) - 1):
        v2 = vec[i]
    solve(v1, v2)
for i in range(H):
    print(*A[i])
N = int(input())
a = list(map(int,input().split()))


mydict = {}
for i in range(N):
    mydict = {i:0}


for i in range(N):
    if a[i] > N:
        mydict[a[i]] += 1 
        N -= 1

for i in range(1:N):
    print(mydict[a[i]])

    

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
M = N
W = N

mydict = {}
for i in range(N):
    mydict[i] = 0


for i in range(len(a)):
    if M-a[i] <= N:
        mydict[a[i]-1] += 1 
        N -= 1
        M -= a[i]

for i in range(W):
    print(mydict[i])
from collections import deque
HW = input(),split()
H, W = int(HW[0]), int(HW[1])
C = input()split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    tmpr = input().split()
    route.append(tmp)
'''
H, W = 4, 4
Ch, Cw = 1, 1
Dh, Dw= 4, 4
route = [[".",".","#","."],[".",".","#","."],[".","#",".","."],[".","#",".","."]]
'''
visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.pop()
        elif len(warpkouho) != 0:
            tmp = warpkouho.pop()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
        
        

### FIXED CODE ###

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
import math
K=input()

if K%7=0:
    L=9*K/7
else:
    L=9*K

if L%2=0 or L%5=0:
    print(-1)
else:
    r=10%L
    for i in range(1,10**6+1):
        if r==1:
            ans=i
            break
        else:
            r=10*r%L

print(ans)

### FIXED CODE ###

import math
K=int(input())

if K%7==0:
    L=9*K//7
else:
    L=9*K

if L%2==0 or L%5==0:
    ans=-1
else:
    r=10%L
    for i in range(1,10**6+1):
        if r==1:
            ans=i
            break
        else:
            r=10*r%L
print(ans)
# 大きさnの順列をすべて生成する
from itertools import permutations
def generate_permutations(n):
    perms = permutations(range(1, n+1), n)
    return [perm for perm in perms]

n = int(input())
ptuple = tuple(map(int, input().split()))
qtuple = tuple(map(int, input().split()))

perms = generate_permutations(n)
a = perms.index(ptuple)
b = perms.index(qtuple)
print(int(math.fabs(a - b)))

### FIXED CODE ###

k, x = map(int, input().split())

if 500 * k  >= x:
    print('Yes')
else:
    print('No')
from collections import deque
from sys import stdin, setrecursionlimit
input = stdin.readline

setrecursionlimit(100000)

def DFS(x,y):
    #global blocknum
    if mapmatrix[y][x] == '.' and blocknumlist[y][x] == -1:
        #blocknumlist[y][x] = blocknum
        num = blocknumlist[y][x]
        for dx, dy in move:
            X = x + dx; Y = y + dy
            if X == Dw and Y == Dh:
                print(num)
                exit()
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blocknumlist[Y][X] == -1 and mapmatrix[Y][X] == '.':
                    blocknumlist[Y][X] = num
                    DFS(X,Y)
        for dx, dy in move2:
            X = x + dx; Y = y + dy
            if X == Dw and Y == Dh:
                print(num + 1)
                exit()
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if blocknumlist[Y][X] == -1 and mapmatrix[Y][X] == '.':
                    blocknumlist[Y][X] = num + 1
                    DFS(X,Y)

H,W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
mapmatrix = [None]*H
for i in range(H):
    mapmatrix[i] = list(input())

move = ((1,0),(-1,0),(0,-1),(0,1))
move2 = ((2,0),(-2,0),(0,-2),(0,2),(1,1),(-1,-1),(1,-1),(-1,1))
blocknumlist = [[-1]*W for _ in range(H)]
blocknum = 0

DFS(Cw,Ch)
print(-1)

### FIXED CODE ###

from itertools import product
from collections import deque
from sys import stdin
input = 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 = [None]*H
for i in range(H):
    S[i] = list(input())

moveA = ((1,0),(0,1),(-1,0),(0,-1))
moveB = []
for i,j in product((-2,-1,0,1,2), repeat=2):
    if (i,j) not in moveA:
        moveB.append((i,j))

mapmatrix = [[-1]*W for _ in range(H)]
queue = deque()
queue.append((Cw,Ch))
mapmatrix[Ch][Cw] = 0

worpqueue = deque()
worpqueue.append((Cw,Ch))
while queue or worpqueue:
    while queue:
        x,y = queue.popleft()
        worpnum = mapmatrix[y][x]

        for dx, dy in moveA:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if mapmatrix[Y][X] == -1 and S[Y][X] == '.':
                    mapmatrix[Y][X] = worpnum
                    queue.append((X,Y))
                    worpqueue.append((X,Y))
                    
    nextworpqueue = deque()
    while worpqueue:
        x,y = worpqueue.popleft()
        worpnum = mapmatrix[y][x]

        for dx, dy in moveB:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if mapmatrix[Y][X] == -1 and S[Y][X] == '.':
                    mapmatrix[Y][X] = worpnum + 1
                    queue.append((X,Y))
                    nextworpqueue.append((X,Y))
    
    while nextworpqueue:
        x,y = nextworpqueue.popleft()
        worpqueue.append((x,y))
        
print(mapmatrix[Dh][Dw])