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

# -*- coding: utf-8 -*-
from functools import reduce

n = int(input()) 
alist = list(map(int, input().split()))
 
def gcd2(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def gcd(*numbers):
    return reduce(gcd2, numbers)

if len(alist) == 2:
  ans = max(alist)
else:
  ansList = []
  for i in range(len(alist)):
    srList = alist[:]
    del srList[i]
    gcdval = gcd(*srList)
    ansList.append(gcdval)
  ans = max(ansList)
print("{}".format(ans))

### FIXED CODE ###

from fractions import gcd
N = int(input())
a = list(map(int, input().split()))
l = [0] * N
r = [0] * N
m = [0] * N

for i in range(N):
  if i == 0:
    l[i] = 0
  else:
    l[i] = gcd(l[i-1], a[i-1])

for j in reversed(range(N)):
  if j == N - 1:
    r[j] = 0
  else:
    r[j] = gcd(r[j+1], a[j+1])
    
for k in range(N):
#  print(r[k], l[k])
  m[k] = gcd(r[k], l[k])
  
print(max(m))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [_+1 for _ in range(n)]
ans = [0 for _ in range(n)]
for i in range(n):
  x = a.index(l[i])
  ans[i] = str(x+1)
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  ans[a[i]-1] += i+1
  ans[a[i]-1] = str(ans[a[i]-1])
print(" ".join(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
PY_list = [list(map(int, input().rstrip().split())) for i in range(M)]
#-----

# key= int, Number of Prefecture
# value= list, BirthYear of city
pref_dic={}

for p,y in PY_list:
    pref_dic.setdefault(p,[])
    pref_dic[p] += [y]

for k in pref_dic:
    pref_dic[k].sort()

for m in range(M):
    inum_pref = PY_list[m][0]
    inum_city = pref_dic[ inum_pref ].index( PY_list[m][1] ) + 1
    print('{0:06}{1:06}'.format(inum_pref, inum_city))


### FIXED CODE ###

# -*- coding: utf-8 -*-

N,M = list(map(int, input().rstrip().split()))
PY_list = [list(map(int, input().rstrip().split())) for i in range(M)]
#-----

## key= int, Number of Prefecture
## value= list, BirthYear of city
pref_dic={}

for p,y in PY_list:
    pref_dic.setdefault(p,[])
    pref_dic[p] += [y]

for k in pref_dic:
    pref_dic[k].sort()

## key= int, BirthYear of city
## value= int, Index of BirthYear-list in each Prefecture
city_dic={}

for k in pref_dic:
    for i,year in enumerate( pref_dic[k] ):
        city_dic.setdefault(year,-1)
        city_dic[year] = i

for m in range(M):
    inum_pref = PY_list[m][0]
    #inum_city = pref_dic[ inum_pref ].index( PY_list[m][1] ) + 1
    inum_city = city_dic[ PY_list[m][1] ] + 1
    print('{0:06}{1:06}'.format(inum_pref, inum_city))
### BUGGY CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
sum1 = 0
sumMax = 0
for i in range(N-K+1):
    for j in range(K):
        sum1 = sum1 + p[i+j]
    if(sumMax < sum1):
        sumMax = sum1
    sum1 = 0
result = 0.5*K + 0.5*(sumMax)
print(result)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
S = [0]
a = 0
sum1 = 0
sumMax = 0
for i in range(N):
    a += p[i]
    S.append(a)
for i in range(N-K+1):
    sum1 = S[i+K] - S[i]
    if(sumMax < sum1):
        sumMax = sum1
result = 0.5*K + 0.5*(sumMax)
print(result)
### BUGGY CODE ###

import math

def P(n, r):
    if n < r:
        return 0
    return math.factorial(n)//math.factorial(n-r)
 
 
def C(n, r):
    return P(n, r)//math.factorial(r)


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

for i in range(n):
    if E.count(a[i]) == 0:
        E.append(a[i])

num = [0] * len(E)
comb = [0] * len(E)

for i in range(len(E)):
    num[i] = a.count(E[i])
    comb[i] = C(num[i], 2)

count = sum(comb)

for i in range(n):
    l = E.index(a[i])
    print(count - comb[l] + C(num[l]-1, 2))

### FIXED CODE ###


from collections import Counter

def C(n):
    if n < 2: return 0
    return n * (n-1) // 2    
    
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)

count = 0

for i, j in c.items():
    count += C(j)

for i in a:
    m = c[i]
    print(count - m + 1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from operator import itemgetter
def main():
    h,n=map(int,input().split())
    lis=[]
    for i in range(n):
        lis.append(tuple(map(int,input().split())))
    lis.sort(key=itemgetter(1))
    dp=[10**10]*(h+1)
    dp[0]=0
    for l in lis:
        a,b=l[0],l[1]
        for i in range(1,h+1):
            dp[i]=min(dp[i],min(dp[max(i-a,0):i])+b)
    print(dp[h])



if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for l in lis:
        dp[1:l[0]+1]=np.minimum(dp[1:l[0]+1],l[1])
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[h])

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

N = int(input())
A = list(map(int,input().split()))
exc = []
ls = []
for a in A:
    if a < 3200:
        ls.append(a)
    else:
        exc.append(a)
rates = [list(range(1,400))]+[list(range(400*i,400*i+399)) for i in range(1, 8)]
vars = [False]*8
for r in ls:
    for j in range(8):
        if r in rates[j]:
            vars[j] = True
if ls == []:
    print(1, min(len(exc), 8))
else:
    ans = vars.count(True)
    if exc == []:
        print(ans, ans)
    else:
        while True:
            ans = 0
        print(ans, min(ans+len(exc), 8))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
exc = []
ls = []
for a in A:
    if a < 3200:
        ls.append(a)
    else:
        exc.append(a)
rates = [list(range(1,400))]+[list(range(400*i,400*i+400)) for i in range(1, 8)]
vars = [False]*8
for r in ls:
    for j in range(8):
        if r in rates[j]:
            vars[j] = True
ans = vars.count(True)
if ans == 0:
    print(1, ans+len(exc))
else:
    print(ans, ans+len(exc))
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())


    def f(i):
        l = []
        for a in range(1, math.floor(math.sqrt(i))):
            l.append(a)
        l_list = list(itertools.combinations_with_replacement(l, 3))
        count = 0
        for j in range(len(l_list)):
            x = l_list[j][0]
            y = l_list[j][1]
            z = l_list[j][2]
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if ans == i and x == y and y == z:
                count += 1
            elif ans == i:
                count += 3
        return count

    for i in range(1, n+1):
        count = f(i)
        if count != 0:
            print(count)
        else:
            print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    l = [0]*(n+1)
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                temp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if temp <= n:
                    l[temp] += 1

    for i in range(1, n+1):
        print(l[i])


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

n=int(input())

def make_div(n):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:# 平方数の時を考慮
                div.append(n//i)

    div.sort()
    return div

ans=0
for i in range(1,n):
    ans+=len(make_div(i))
print(ans)

### FIXED CODE ###

n=int(input())

ans=0
for i in range(1,n):
    ans+=(n-1)//i
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())

rev=1

for _ in range(0,q):
  n=input().split()
  x=[]
  if n[0]=="1":
    rev*=-1
  else:
    if (n[1]=="1" and rev==1) or (n[1]=="2" and rev==-1):
      x.append(n[2])
      x.append(s)
      s=''.join(x)
#      s=n[2]+s
    else:
      x.append(s)
      x.append(n[2])
      s=''.join(x)
#      s=s+n[2]
if rev==1:
  print(s)
else:
  print(s[::-1])


### FIXED CODE ###

s=input()
q=int(input())

rev=1

sf=""
sb=s

for _ in range(0,q):
  n=input().split()
  if n[0]=="1":
    rev*=-1
  else:
    if (n[1]=="1" and rev==1) or (n[1]=="2" and rev==-1):
      sf+=n[2]
    else:
      sb+=n[2]

s=sf[::-1]+sb

if rev==1:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

from fractions import gcd
k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=gcd(a,gcd(b,c))
print(ans)

### FIXED CODE ###

from fractions import gcd
k=int(input())
ans=0
gcd_table=[0]*(k+1)
for a in range(1,k+1):
    for b in range(1,k+1):
        gcd_table[gcd(a,b)]+=1
for g in range(1,k+1):
    for c in range(1,k+1):
        ans+=gcd(g,c)*gcd_table[g]
print(ans)
### BUGGY CODE ###

from itertools import product

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

# bit DP...?
dp = [[0] * (2 ** n) for i in range(n + 1)]
dp[0][0] = 1

for i in range(n + 1):
    for j, bit in enumerate(product([0, 1], repeat=n)):
        if i == sum(bit):
            for num,k in enumerate(bit):
                if k == 1:
                    dp[i][j] += dp[i - 1][j - 2 ** (n - num - 1)] * a[i - 1][num]

print(dp[n][2 ** n - 1])



### FIXED CODE ###

mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
sum = 0
s.insert(0, 0)
s.insert(n+1, 0)
for i in range(1,n+1):
    st = s[i]
    s.pop(i)
    for j in range(n):
        sum += abs((s[j])-(s[j+1]))
    print(sum)
    s.insert(i, st)
    sum = 0

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
sum = 0
s.insert(0, 0)
s.insert(n+1, 0)
for i in range(n+1):
    sum += abs((s[i])-(s[i+1]))
for j in range(1,n+1):
    print(sum - abs(s[j-1]-s[j]) - abs(s[j]-s[j+1]) +abs(s[j-1]-s[j+1]))
### BUGGY CODE ###

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
#print(n,k,a)
mydict={}
mylist=[]
for i in a:
    if i not in mydict:
        mydict[i]=a.count(i)

for i in mydict.values():
  mylist.append(i)
mylist.sort()      
z=len(mydict)-k
#print(mydict)
if z==0:
    print(0)
else:

    ans=0
    for i in range(z):
        ans+=mylist[i]
    print(ans)

### FIXED CODE ###

import collections

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]

mydata=collections.Counter(a)
mylist=list(mydata.values())
mylist.sort(reverse=True)
#print(mylist)

if len(mylist)<k:
  print(0)
else:
  val=sum(mylist[:k])
  print(n-val)
### BUGGY CODE ###

n = int(input())
p = [int(input()) for _ in range(n)]

a = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for x in p:
    a[x][x] = 1
    for i in range(1, x):
        if a[i][x - 1] == 1:
            a[i][x] = 1

ans = 0
for i in range(1, n + 1):
    ans = max(ans, sum(a[i]))

print(n - ans)

### FIXED CODE ###

n = int(input())
p = [int(input()) for _ in range(n)]

q = [n for _ in range(n)]
for i in range(n):
    q[p[i] - 1] = i

stay_num_cnt = 0
cnt = 0
t = 0
for x in q:
    if x >= t:# x == tはあり得ない
        cnt += 1
    else:
        cnt = 1
    t = x
    stay_num_cnt = max(stay_num_cnt, cnt)
print(n - stay_num_cnt)#, q)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
import heapq
heapq.heapify(a)
#print(a)
for _ in range(m):
  b, c = map(int, input().split())
  for _ in range(b):
    if a[0] >= c: break
    heapq.heappop(a)
    heapq.heappush(a, c)
  #print(a)
ans = sum(a)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
d = []
for _ in range(m):
  b, c = map(int, input().split())
  d.append((b, c))
d.sort(key=lambda x: x[1], reverse=True)
l = 0
for bc in d:
  a.extend([bc[1] for _ in range(bc[0])])
  l += bc[0]
  if l > n: break
desc = sorted(a, reverse=True)
ans = sum(desc[:n])
print(ans)
### BUGGY CODE ###

def solve():
    
    A, B, C, D, E, F = map(int, input().split())
    memo = {}
    
    for a in range(31):
        for b in range(31):
            for c in range(101):
                for d in range(101):
                    if a == 0 and b == 0:
                        continue
                    if (100*A)*a + (100*B)*b + C*c + D*d > F:
                        continue
                    if C*c + D*d > E:
                        continue
                    density = 100 * (C*c+D*d) / ( (100*A)*a + (100*B)*b + C*c + D*d )
                    memo[a,b,c,d] = density
    
    max_v = max(memo.values())
    
    for k, v in memo.items():
        if v == max_v:
            print((100*A)*k[0] + (100*B)*k[1] + min(C*k[2] + D*k[3], E), min(C*k[2] + D*k[3], E) )
            break

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    
    A, B, C, D, E, F = map(int, input().split())
    memo = {}
    
    for a in range(31):
        for b in range(31):
            for c in range(101):
                for d in range(101):
                    if a == 0 and b == 0:
                        break
                    if (100*A)*a + (100*B)*b + C*c + D*d > F:
                        break
                    if  ((100*A)*a + (100*B)*b)/100 *E < C*c + D*d:
                        break
                    density = 100 * (C*c+D*d) / ( (100*A)*a + (100*B)*b + C*c + D*d )
                    memo[a,b,c,d] = density
    
    max_v = max(memo.values())
    
    for k, v in memo.items():
        if v == max_v:
            print((100*A)*k[0] + (100*B)*k[1] + C*k[2] + D*k[3], C*k[2] + D*k[3] )
            break
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import itertools
import heapq
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = []
for i in comb:
  l.append(list(i))
  
A = []
A_append = A.append
one = [1]*len(l)
for j in range(k):
  for i in range(len(l)):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import copy

def solve():
    INF = 2*(10**8)+1
    N, K = list(map(int, input().split(" ")))
    X = [0]
    X.extend(list(map(int, input().split(" "))))
    X.sort()
    
    def dfs(depth, i, Xs):
        if depth == K:
            return 0
        
        ret1, ret2 = INF, INF
        Xs2 = copy.deepcopy(Xs)
        if i+1 < len(Xs):
            # 右に移動
            cost = abs(Xs[i] - Xs[i+1])
            del Xs[i]
            ret1 = dfs(depth+1, i, Xs) + cost
        if i-1 >= 0:
            # 左に移動
            cost = abs(Xs2[i] - Xs2[i-1])
            del Xs2[i]
            ret2 = dfs(depth+1, i-1, Xs2) + cost
        
        return min(ret1, ret2)

    # 0座標のインデックスは？
    for i in range(len(X)):
        if X[i] == 0:
            break
    ans = dfs(0, i, X)
    print(ans)


if __name__ == "__main__":
    solve()

### FIXED CODE ###

# -*- coding:utf-8 -*-

"""解説
https://www.youtube.com/watch?v=5O4k1n5Ejzw

区間を考える問題

-30 -10 0 10 20 50

・K = 3のとき、

0座標を必ず含める、ある連続するK個のロウソクについて考える

・-30 -10 0 10
・-10 0 10 20
・0 10 20 50

左端と右端に到達する最小値を求めていけばよくて、間のロウソクは無視してよい（必ず移動中に火をつけるので）

すべての場合について求めて、その中の最小値が答え
"""
def solve():
    N, K = list(map(int, input().split()))
    X = list(map(int, input().split()))
    if 0 in X:
        # 0座標にロウソクがあるなら、火をつけるロウソクをひとつ減らしてよい
        K -= 1
    else:
        X.append(0)
    X.sort()

    origin_i = X.index(0)
    left_i = max(origin_i-K, 0)

    INF = 10**12
    ans = INF
    while left_i <= origin_i:
        if left_i+K < len(X):
            tmp1 = abs(X[left_i]-0)*2 + abs(X[left_i+K]-0)
            tmp2 = abs(X[left_i]-0) + abs(X[left_i+K]-0)*2
        else:
            break
        ans = min(ans, tmp1, tmp2)
        left_i += 1
    print(ans)

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

import sys
sys.setrecursionlimit(10**7)
import numpy as np
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    s_list = []
    t_list = []
    x_list = []
    d_list = []
    n, q = map(int, input().split())
    dict_x_by_d = {}
    for i in range(n):
        s, t, x = map(int, input().split())

        s_list.append(s)
        t_list.append(t)
        x_list.append(x)
        for d in range(s-x, (t-1)-x+1):
            if d in dict_x_by_d:
                dict_x_by_d[d] = min(x, dict_x_by_d[d])
            else:
                dict_x_by_d[d] = x
    for i in range(q):
        d = int(input())
        d_list.append(d)
        if d in dict_x_by_d:
            print(dict_x_by_d[d])
        else:
            print(-1)

solve()

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
#print(a)

ans_a = a[n-1]
maxi = 0
idx = 0
for i in enumerate(a):
    val = max(maxi, combinations_count(ans_a, i[1]))
    if maxi < val:
        idx = i[0]
        maxi = val
    #print(idx, maxi)
    else:
        break

ans_b = a[idx]
print(ans_a, ans_b)


### FIXED CODE ###

import math
import numpy

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def get_nearest(li, num):
    index = numpy.abs(numpy.asarray(li) - num).argmin()
    return li[index]

n = int(input())
a = [int(_) for _ in input().split()]

if n == 2:
    print(max(a), 0)
    exit()

ans_a = max(a)
ans_b = get_nearest(a, ans_a/2)

print(ans_a, ans_b)
### BUGGY CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = []
for i in range(H):
    S.append(input())

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.appendleft((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)



### FIXED CODE ###

import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

H, W = inpl()
ch, cw = inpl()
dh, dw = inpl()
ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = []
for i in range(H):
    S.append(input())

dist = []
INF = 1001001001
for i in range(H):
    dist.append([INF for i in range(W)])

q = deque([])
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    # 歩き回る
    for i, j in ((1,0),(-1,0),(0,1),(0,-1)):
        if not 0 <= h + i < H:
            continue
        if not 0 <= w + j < W:
            continue
        if S[h+i][w+j] == '#':
            continue
        if dist[h][w] < dist[h+i][w+j]:
            dist[h+i][w+j] = dist[h][w]
            q.appendleft((h+i, w+j))
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not 0 <= h + i < H:
                continue
            if not 0 <= w + j < W:
                continue
            if S[h+i][w+j] == '#':
                continue
            if dist[h][w] + 1 < dist[h+i][w+j]:
                dist[h+i][w+j] = dist[h][w] + 1
                q.append((h+i, w+j))

print(dist[dh][dw] if dist[dh][dw] != INF else -1)



# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)