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

#!/usr/bin/env python3
import sys
from math import factorial
from functools import lru_cache

def fact(x: int):
    if(x == 0 or x == 1):
        return 1
    if(dp[x] != 0):
        return dp[x]
    else:
        dp[x] = x * fact(x-1)
        
    return dp[x]

@lru_cache(maxsize=1000000000)
def comb(n: int, r: int):
    # return fact(n) // (fact(r)*fact(n-r))
    return factorial(n) // (factorial(r)*factorial(n-r))


# dp = [0] * 1000000000

def solve(n: int, a: "List[int]"):
    a.sort()

    ai,aj = 0,0
    ans = 0
    for i in range(n-1, -1, -1):
        p = n // 2
        if(p == 0):
            p = p+1
        elif(p == n-1):
            p = p-1
        x = a[p]
        while(True):
            if(a[i] > a[p]):
                if(0 < p < n and comb(a[i], a[p-1]) > comb(a[i], a[p])):
                    p = p-1
                elif (0 <= p < n-1 and comb(a[i], a[p+1]) > comb(a[i], a[p])):
                    p = p+1
                else:
                    if(comb(a[i],a[p]) > ans):
                        ans = comb(a[i],a[p])
                        ai,aj = a[i],a[p]
                    break
                
            else:
                break
    
    print(ai,aj)
    
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n)]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import factorial
from functools import lru_cache

def fact(x: int):
    if(x == 0 or x == 1):
        return 1
    if(dp[x] != 0):
        return dp[x]
    else:
        dp[x] = x * fact(x-1)
        
    return dp[x]

# @lru_cache(maxsize=1000000000)
def comb(n: int, r: int):
    # return fact(n) // (fact(r)*fact(n-r))
    return factorial(n) // (factorial(r)*factorial(n-r))


# dp = [0] * 1000000000

def solve(n: int, a: "List[int]"):
    a.sort()

    m = a[-1]
    print(m, min(a, key=lambda x:abs(m-x*2)))
    
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n)]  # type: "List[int]"
    solve(n, a)

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

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


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)


### FIXED CODE ###

from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]


friend = [set() for _ in range(N)]
block = [set() for _ in range(N)]

answer = [set() for _ in range(N)]

A = [0 for _ in range(N)]


for a, b in AB:
  friend[a-1].add(b)
  friend[b-1].add(a)

for c, d in CD:
  block[c-1].add(d)
  block[d-1].add(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    answer[root-1].add(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i] - friend[i] - block[i])

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


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]

# 木の根を求める
def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]
# x, y の属する集合を併合
def unite(x, y):
  rx = find(x)
  ry = find(y)
  if rx == ry:
    return
  if rank[rx-1] < rank[ry-1]:
    rx, ry = ry, rx
  par[ry-1] = rx
  size[rx-1] += size[ry-1]
  if rank[rx-1] == rank[ry-1]:
    rank[rx-1] += 1
# x, y が同じ集合に属するか否か
def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

ans = [0 for _ in range(N)]

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = {i:[] for i in range(N)}
AB = [[0] * 2 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    AB[i][0], AB[i][1] = a, b
    if i == 0:
        start = a

K = 0
for some in graph.values():
    K = max(len(some), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(start)
color_num = {i:{} for i in range(N)}
dist[start] = True

# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v].values():
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break
# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[AB[i][0]][AB[i][1]])

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
### BUGGY CODE ###

# 2125
n = int(input())
get_inf = list(map(int, input().split(' ')))
a = get_inf[::2]
b = get_inf[1::2]

def count_unique(lis):
    r = []
    s = []
    i = 0
    while i < len(lis):
        count = 1
        k = i + 1
        if lis[i] > 0:
            while k < len(lis):
                if lis[i] == lis[k] and lis[k] > 0:
                    count += 1
                    lis[k] *= -1
                k += 1
            r.append(count)
            s.append(lis[i])
            lis[i] *= -1
            i += 1
        else:
            i += 1
    return r, s

x = []
x_1 = []
y = []
y_1= []
x, x_1 = count_unique(a)
y, y_1 = count_unique(b)
x.append(0)
y.append(0)

if x_1[x.index(max(x))] != y_1[y.index(max(y))]:
    print(n-max(x)-max(y))
else:
    p = max(x)
    q = max(y)
    x[x.index(max(x))] *= -1
    y[y.index(max(y))] *= -1
    print(min([n-p-max(y), n-q-max(x)]))

### FIXED CODE ###

import collections
n = int(input())
v = list(map(int, input().split(' ')))
a = v[::2]
b = v[1::2]

a_count = []
b_count = []

a_count = collections.Counter(a).most_common(3)
b_count = collections.Counter(b).most_common(3)

if a_count[0][0] != b_count[0][0]:
    print(n-int(a_count[0][1])-int(b_count[0][1]))
else:
    if len(a_count)!= 1 and len(b_count)!= 1:
        print(min(n-int(a_count[0][1])-int(b_count[1][1]),n-int(a_count[1][1])-b_count[0][1]))
    elif len(a_count) == 1 and len(b_count)!=1:
        print(n-int(a_count[0][1])-int(b_count[1][1]))
    elif len(b_count)==1 and len(a_count)!= 1:
        print(n-int(a_count[1][1])-int(b_ocunt[0][1]))
    else:
        print(int(n/2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())
### BUGGY CODE ###

import sys
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        a_ls += [(a[x], x, y)]

a_ls.sort(key=lambda x:x[0])
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    _sum = 0
    for ind in range(l, r, d):
        ind -= 1
        start = a_ls[ind]
        goal = a_ls[ind+d]
        _sum += abs(start[2] - goal[2]) + abs(start[1] - goal[1])
    print(_sum)

### FIXED CODE ###

import sys
import bisect
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        a_ls += [(a[x], x, y)]

a_ls.sort(key=lambda x:x[0])
diff_ls = []
for ind in range(h*w):
    if ind < d:
        diff_ls.append(0)
    else:
        start = a_ls[ind-d]
        goal = a_ls[ind]
        diff = diff_ls[ind-d] + abs(start[2] - goal[2]) + abs(start[1] - goal[1])
        diff_ls.append(diff)
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    print(diff_ls[r] - diff_ls[l])
### BUGGY CODE ###

n=int(input())
s=input()

count=0

i=0
while i < n:
  si = s[i]
  j = i + 1
  while j < n:
    sj = s[j]
    if si != sj:
      k = j + 1
      while k < n:
        sk = s[k]
        if si != sk and sj != sk and (j - i) != (k - j):
          count += 1
        k += 1
    j += 1
  i += 1
  
print(count)

### FIXED CODE ###

n=int(input())
s=input()

r=0
g=0
b=0
count=0

for i in s:
  if i == "R":
    r += 1
  elif i == "G":
    g += 1
  elif i == "B":
    b += 1

count = r*g*b

# k-j==j-iの場合を引く
for i in range(n-2):
  si = s[i]
  for j in range(i+1,i+(n-i-1)//2+1):
    if si != s[j]:
      sj = s[j]
      k = j+(j-i)
      if s[k] != si and s[k] != sj:
        count -= 1
        
print(count)
### BUGGY CODE ###

import collections
N,K=map(int,input().split())
A=map(int,input().split())
B=collections.Counter(A).most_common()
print(sum(B[K:][i][1] for i in range(len(B[K:]))))

### FIXED CODE ###

from collections import Counter
N,K=map(int,input().split())
A=input().split()
B=Counter(A)
C=sorted(B.values(),reverse=True)
print(sum(C[K:]))
### BUGGY CODE ###

import copy
import functools
import fractions
import sys
input = sys.stdin.readline

n=int(input())
lstA=list(map(int,input().split()))
gcdlst=[None]*n

for i in range(n):
    cplstA=copy.copy(lstA)
    del cplstA[i]
    gcdlst[i]=functools.reduce(fractions.gcd, cplstA)

print(max(gcdlst))

### FIXED CODE ###

#import sys
#input=sys.stdin.readline

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    gcdA = [0]*n
    gcdB = [0]*n
    gcdA[0] = A[0]
    gcdB[n-1] = A[n-1]
    for i in range(1, n):
        gcdA[i] = gcd(A[i], gcdA[i-1])
        gcdB[n-i-1] = gcd(A[n-i-1], gcdB[n-i])
    ans = max(gcdA[n-2], gcdB[1])
    for i in range(1, n-1):
        ans = max(ans, gcd(gcdA[i-1], gcdB[i+1]))
    print(ans)


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

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = list(map(int, input().split()))
B = sorted(list(map(int, input().split())))

from bisect import bisect_left, bisect_right

ans = 0
for k in range(38):
    mod = 2**(k+1)
    T = 2**k
    Bcopy = sorted(list(map(lambda x:x%mod, B)))
    count = 0
    for a in A:
        a = a % mod
        i1 = bisect_left(Bcopy, T-a)
        i2 = bisect_right(Bcopy, 2*T-a-1 )
        i3, i4 = bisect_left(Bcopy, 3*T-a), \
                 bisect_right(Bcopy, 4*T-a-1)
        count += i2 -i1 + i4 - i3
        # print("T: {}, a: {} , i1,i2,i3,i4: {}, Bcopy: {}, T-a: {}, 2*T-a: {}".format(T,a, [i1,i2,i3,i4], Bcopy,
        #          T-a, 2*T-a))
    if not count % 2 == 0:
        ans |= 1<<k
print(ans)
        


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = list(map(int, input().split()))
B = sorted(list(map(int, input().split())))

from bisect import bisect_left, bisect_right
from copy import copy

ans = 0
for k in range(38):
    mod = 2**(k+1)
    T = 2**k
    A_sub = [ [], [] ]
    B_sub = [ [], [] ]
    for a in A:
        A_sub[ (a & (1<<k))>>k].append(a)
    for b in B:
        B_sub[ (b & (1<<k))>>k].append(b)

    A = sum(A_sub, [])
    B = sum(B_sub, [])

    itr = [N]*4
    count = 0
    mask = 2**(k+1)-1
    amask = [ai & mask for ai in A]
    bmask = [bi & mask for bi in B]
    for ai in amask:
        border = [
                T - ai,
                2*T - ai,
                3*T - ai,
                4*T - ai]
        for i in range(4):
            while 0 < itr[i]  and border[i] <= bmask[itr[i]-1]:
                itr[i] -= 1
        count += (itr[1] - itr[0]) + (itr[3]) - (itr[2])


    # Bcopy = list(map(lambda x: x%mod, B))

    # count = 0
    # for a in A:
    #     a = a % mod
    #     i1 = bisect_left(Bcopy, T-a)
    #     i2 = bisect_right(Bcopy, 2*T-a-1 )
    #     i3, i4 = bisect_left(Bcopy, 3*T-a), \
    #              bisect_right(Bcopy, 4*T-a-1)
    #     count += i2 - i1 + i4 - i3
    #     # print("T: {}, a: {} , i1,i2,i3,i4: {}, Bcopycopy: {}, T-a: {}, 2*T-a: {}".format(T,a, [i1,i2,i3,i4], Bcopy,
    #     #          T-a, 2*T-a))
    if not count % 2 == 0:
        ans |= 1<<k
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
import math
def main():
    N, P = map(int, input().split())
    S = input().rstrip("\r\n")[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if int(S[i]) % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        for i in range(N):
            D[i] = int(S[:i+1][::-1]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = str(input())
ans = 0

for i in range(len(S)-4):
    for j in range(i+3, len(S)):
        if int(S[i:j+1]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])
### BUGGY CODE ###

from collections import *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]

for h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while P:
  x1,y1 = P.popleft()
  Q.append([x1,y1])
  for dx,dy in move:
    x = x1+dx
    y = y1+dy
    if ans[x][y]==-1:
      ans[x][y] = ans[x1][y1]
      P.append([x,y])
  
  if len(P)==0:
    while Q:
      x2,y2 = Q.popleft()
      for dx,dy in magic:
        x = x2+dx
        y = y2+dy
        if ans[x][y]==-1:
          ans[x][y] = ans[x2][y2]+1
          P.append([x,y])

print(ans[dh+1][dw+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()