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

def func(x,y):
    return min(x,y)

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [float("inf")] * (2*self.n-1)

    def update(self, k, a): #0_indexed
        k += self.n - 1
        self.arr[k] = a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = min(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):
        L, R = l+self.n, r+self.n
        ide_ele = float("inf")
        #単位元(ide_ele)は、区間外の値などに設定する値です。
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0
        res = ide_ele
        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1]) #

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res


import sys
input=sys.stdin.readline
n,m=map(int,input().split())

sg=SegmentTree(n+1)
sg.update(1,0)
lrc=[tuple(map(int,input().split())) for _ in range(m)]
lrc.sort(key=lambda x:x[0])
for _ in range(m):
    l,r,c=lrc[_]
    x=sg.query(l,l+1)
    if x!=float("inf"):
        x+=c
        for i in range(l,r+1):
            sg.update(i,min(x,sg.query(i,i+1)))

print(sg.query(n,n+1) if sg.query(n,n+1)!=float("inf") else -1)


### FIXED CODE ###


from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
g=Graph()

for _ in range(m):
    l,r,c=map(int,input().split())
    g.add_edge(l,r,c)
for i in range(2,n+1):
    g.add_edge(i,i-1,0)


d = Dijkstra(g,1)
ans=d.shortest_distance(n)
print(ans if ans!=float("inf") else -1)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement 
def main():
    s = readline().rstrip().decode()
    K = int(readline())
    N = len(s)
    p = [int(i) for i in range(N)]
    S = set()
    for l, r in combinations_with_replacement(p, 2):
        S.add(s[l:r+1])
    lis = list(S)
    lis.sort()
    print(lis[K-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000)

def main():
    s = readline().rstrip().decode()
    K = int(readline())
    #sに含まれる文字を一文字ずつ抽出する.
    #ここで抽出した文字を組み合わせて辞書順に文字列を構成していく
    #K<=5だから高々26^5個の文字列を構成することになる
    l = sorted(list(set(s)))
    #cnd:=構成した文字列を辞書順に格納するリスト
    cnd = []
    #f(sub):=subから構成可能なK文字以下のSの部分文字列を構成する関数
    def f(sub):
        cnd.append(sub)
        if len(sub) < K: 
            #lから選んでsubに一文字追加する
            for i in l:
                nx = sub+i
                if nx in s:
                    f(nx)
    for i in l:
        f(i) 
    print(cnd[K-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import copy
import fractions as f


n = int(input())
a = list(map(int, input().split()))
b = copy.deepcopy(a)
ans = 1

for e in b:
    if (len(a) == 1):
        ans = a[0]
    elif (len(a) == 2):
        ans = max(a[0], a[1])
    else:
        a.remove(e)
        rep = a[0]

        for elem in a:
            rep = f.gcd(rep, elem)

        if (ans < rep):
            ans = rep

        a.append(e)

print(ans)


### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
middle = [0] * (n + 1)

for i in range(0, n - 1):
    left[i + 1] = gcd(left[i], a[i])

for i in range(n - 1, 0, -1):
    right[i] = gcd(right[i + 1], a[i])

for i in range(n):
    middle[i] = gcd(left[i], right[i + 1])

print(max(middle))
### BUGGY CODE ###

N,K = list(map(int, input().split()))
h = list(map(int, input().split()))

dp = {}
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    tm = []
    for j in range(1, min(K+1, i+1)):
        tm.append(dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min(tm)

print(dp[N-1])

### FIXED CODE ###

N,K = list(map(int, input().split()))
h = list(map(int, input().split()))

dp = {}
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2, N):
    tm = []
    for j in range(1, min(K+1, i+1)):
        tm.append(dp[i-j] + abs(h[i-j] - h[i]))
    dp[i] = min(tm)

print(dp[N-1])
### BUGGY CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
limit, mul, m = n-k+1, [], 1
for i in range(limit):
    if i == 0:
        for j in a[i: k+i]:
            m *= j
    else:    
        print('Yes' if m < (m//a[i-1])*a[k+i-1] else 'No')
        m = (m//a[i-1])*a[k+i-1]

### FIXED CODE ###

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

for i in range(n - k):
    if a[k+i] > a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#!/usr/bin/python3
inf = float('inf')

def inf_matrix(n):
    return [[inf for i in range(n)] for j in range(n)]

def sssp(r, w):
    V = len(w)
    result = inf_matrix(V)
    rest = list(range(V))
    rest.remove(r)
    var = [r]
    result[r][r] = 0

    while len(rest) > 0:
        costs = []
        for v in var:
            for res in rest:
                costs.append((result[r][v] + w[v][res], res))
        min_w, min_r = min(costs)
        if min_w == inf:
            break
        rest.remove(min_r)
        var.append(min_r)
        result[r][min_r] = min_w

    return result


def main():
    V, E, r = map(int, input().split())
    w = inf_matrix(V)
    for e in range(E):
        s, t, d = map(int, input().split())
        w[s][t] = d

    result = sssp(r, w)
    for i in range(V):
        if result[r][i] == inf:
            print('INF')
        else:
            print(result[r][i])

main()

### FIXED CODE ###

#!/usr/bin/python3
from collections import defaultdict
from heapq import heappush, heappop

inf = float('inf')

def inf_matrix(n):
    return [[inf for i in range(n)] for j in range(n)]

def dijkstra(r, w, V):
    result = [inf] * V
    q = []
    heappush(q, (0, r))
    result[r] = 0
    while len(q) > 0:
        min_w, min_next = heappop(q)
        for weight, nxt in w[min_next]:
            if result[nxt] > min_w + weight:
                result[nxt] = min_w + weight
                heappush(q, (min_w + weight, nxt))

    return result


def main():
    V, E, r = map(int, input().split())
    w = defaultdict(list)
    for e in range(E):
        s, t, d = map(int, input().split())
        w[s].append((d, t))

    result = dijkstra(r, w, V)
    for i in range(V):
        if result[i] == inf:
            print('INF')
        else:
            print(result[i])

main()
### BUGGY CODE ###

# 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K, Q = MAP()
    A = [INT() for i in range(Q)]
    point = [K for i in range(N)]
    for q in range(Q):
        for j in range(N):
            if j != A[q] - 1:
                point[j] -= 1
    # print(point)
    ans = []
    for i in range(N):
        if point[i] > 0:
            ans.append("Yes")
        else:
            ans.append("No")
    print(*ans)



if __name__ == "__main__":
    main()




### FIXED CODE ###

# 要復習
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N, K, Q = MAP()
    A = [INT() for i in range(Q)]
    point = [K - Q for i in range(N)]
    for a in A:
        point[a-1] += 1
    ans = []
    for i in range(N):
        if point[i] > 0:
            ans.append("Yes")
        else:
            ans.append("No")
    print(*ans)

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

n = list(map(int, input().split()))
N, M = n[0], n[1]

import numpy as np

def main():
    M_list = []
    y_array = np.array([[10000000000]*M]*N)
    for i in range(M):
        tmp = list(map(int, input().split()))
        M_list.append(tmp[0])
        y_array[tmp[0]-1,i] = tmp[1]

    num_array = np.zeros([N,M])
    ynum_array = np.ones([N,M])
    for k in range(N):
        #print(np.argsort(y_array[k]))
        #num_array[k,:] = np.argsort(y_array[k])
        y_sorted = np.sort(y_array)
        tmp = 1
        for l in np.argsort(y_array[k]):
            if int(ynum_array[k][l]) == 10000000000:
                break
            ynum_array[k][l] = tmp
            tmp += 1

    for j in range(M):
        ac = (str(M_list[j]).zfill(6)) + (str(int(ynum_array[M_list[j]-1][j])).zfill(6))
        print(ac)
        
    #print(y_array)

if __name__ == '__main__':
    main()




### FIXED CODE ###

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

city_list = []
for i in range(m):
    p, y = map(int, input().split())
    city_list.append([p, y, i])

city_list.sort(key=lambda x: (x[0], x[1]))

#print(city_list)

tmp_list = [0]*m
tmp_num = 1
for num,j in enumerate(city_list):
    if num == 0:
        tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
        j_tmp = j[0]
        tmp_num += 1
    else:
        if j[0] != j_tmp:
            j_tmp = j[0]
            tmp_num = 1
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1
        else:
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1

for k in tmp_list:
    print(k)
### BUGGY CODE ###

import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 

def SS(L):
    S = [0] * (len(L))
    for i, l in enumerate(L):
        S[i + 1] = S[i] + l

    return S


def main():
    N, X, Y = read_values()
    X -= 1
    Y -= 1
    res = [0] * N

    for i in range(N):
        q = queue.Queue()
        q.put((i, 0))
        close = set()
        while not q.empty():
            s, c = q.get()
            if s in close:
                continue
            
            close.add(s)
            res[c] += 1

            if s + 1 < N and not s + 1 in close:
                q.put((s + 1, c + 1))
            if s > 0 and not s - 1 in close:
                q.put((s - 1, c + 1))
            if s == X and not Y in close:
                q.put((Y, c + 1))
            if s == Y and not X in close:
                q.put((X, c + 1))

    for r in res[1:]:
        print(r // 2)
        
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 


def main():
    N, X, Y = read_values()
    X -= 1
    Y -= 1
    res = [0] * N

    for i in range(N - 1):
        for j in range(i + 1, N):
            d = min(
                j - i,
                abs(X - i) + 1 + abs(Y - j),
                abs(Y - i) + 1 + abs(X - j),
            )

            res[d] += 1

    for r in res[1:]:
        print(r)


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

args = int(input().rstrip())

def snuke(number):
    temp = list(str(number))
    arr = [ int(t) for t in temp] 
    return sum(arr)

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
        if push:
            result.append(i)
        i=i+1
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)

### FIXED CODE ###

args = int(input().rstrip())

def snuke(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

def find_snuke(args):
    result = []
    i = 1
    while len(result) < args:
        push = True
        p = 0
        for power in range(0,len(str(i))):
            if((i+10**power)/snuke(i+10**power))<(i/snuke(i)):
                push = False
                p = power
                break
        if push:
            result.append(i)
        i=i+10**p
            
    return result

arr = find_snuke(args)
for a in arr:
   print(a)
### BUGGY CODE ###

def make_divisors(n):
    cnt = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
    return cnt

n = int(input())
ans = 0
for i in range(1, n):
    ans += make_divisors(i)
print(ans)

### FIXED CODE ###

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

N=int(input())
A=list(map(int,input().split()))
c=0
for i in range(len(A)):
  if A.count(A[i])!=1:
    c=c+1
if c==0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
if len(A) != len(set(A)):
  print("NO")
else:
  print("YES")
### BUGGY CODE ###

h, w, k = map(int, raw_input().split())
arr = [1, 2, 3, 5, 8, 13, 21, 34]


def p(num):
    return max(0, num)


def dp(i, j):

    if i == 0:
        if j == 0:
            r = 1
        else:
            r = 0
    else:
        y = dp(i - 1, j)
        if j - 1 < 0:
            x = 0
        else:
            x = dp(i - 1, j - 1)
        if j + 1 > w - 1:
            z = 0
        else:
            z = dp(i - 1, j + 1)
        r = x * arr[p(j-2)] * arr[p(w-j-2)] + \
            y * arr[p(j-1)] * arr[p(w-j-2)] + \
            z * arr[p(j-1)] * arr[p(w-j-3)]

    return r % (10**9+7)

print dp(h, k-1)

### FIXED CODE ###

h, w, k = map(int, raw_input().split())
arr = [1, 2, 3, 5, 8, 13, 21, 34]


def p(num):
    return max(0, num)

r = [[0 for i in range(w)] for i in range(h+1)]
for i in range(h+1):
    for j in range(w):

        if i == 0:
            if j == 0:
                r[i][j] = 1
            else:
                r[i][j] = 0
        else:
            y = r[i - 1][j]
            if j - 1 < 0:
                x = 0
            else:
                x = r[i - 1][j - 1]
            if j + 1 > w - 1:
                z = 0
            else:
                z = r[i - 1][j + 1]
            r[i][j] = (x * arr[p(j-2)] * arr[p(w-j-2)] + \
                y * arr[p(j-1)] * arr[p(w-j-2)] + \
                z * arr[p(j-1)] * arr[p(w-j-3)]) % (10**9+7)
    

print r[h][k-1]
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
clm = [0] * n

for i in range(n):
    for j in range(i, n-1):
        if h[j] >= h[j+1]:
            clm[i] += 1
        else:
            break


print(max(clm))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))

count = 0
maxcount = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        count += 1
        maxcount = max(count, maxcount)
    else:
        count = 0

print(maxcount)
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

#D
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
num=[[] for i in range(m)]
for i in range(m):
    x,y=map(int,input().split())
    num[i]=[y,x]
num.sort(reverse=True)
for i in range(m):
    for j in range(num[i][1]):
        if a[j]<num[i][0]:
            a[j]=num[i][0]
        else:
            break
    a.sort()

print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[[a[i],1] for i in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    b.append([y,x])
b.sort(reverse=True)
ans=0
cnt=n
for i in range(len(b)):
    use=min(b[i][1],cnt)
    ans+=use*b[i][0]
    cnt-=use
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split(" "))
#Nはポーンの数 Mは入力の数
A=sorted(map(int,input().split(" ")))
L=[list(A)[s]-list(A)[s+1] for s in range(M-1)]

if M<=N:
    print(0)
else:
    for s in range(N-1):
        L.remove(min(L))
    print(abs(sum(L)))

### FIXED CODE ###

N,M=map(int,input().split(" "))
A=list(sorted(map(int,input().split(" "))))
L=[A[s]-A[s+1] for s in range(M-1)]
if M>N:
    print(abs(sum(sorted(L)[N-1:])))
else:
    print(0)
### BUGGY CODE ###

def hantei(n, m, l, d ):
    if (n*10000+m*5000+l*1000)==d:
        return True
    return False

osatu,sum = map(int,input().split())

#n　一万円
#m　五千円
#l　千円
n=m=l=0
result=0

while(n <= osatu):
    while(m <= osatu):
        while(l <= osatu):
            # print("n,m,l",n,m,l)
            if n+m+l == osatu:
                if hantei(n,m,l,sum)==True:
                    print(n,m,l)
                    exit (0)
            l+=1
        l=0
        # if hantei(n,m,l,d)==True:
        #     result += 1
        m+=1
    # if hantei(n,m,l,d)==True:
    #     result += 1
    m=l=0
    n+=1

print("-1 -1 -1")


### FIXED CODE ###

def hantei(n, m, l, d ):
    if (n*10000+m*5000+l*1000)==d:
        return True
    return False

osatu,sum = map(int,input().split())

#n　一万円
#m　五千円
#l　千円
n=m=l=0
result=0

while(n <= osatu):
    while(m+n <= osatu):
        l=osatu-n-m
        if n+m+l==osatu:
            if hantei(n,m,l,sum)==True:
                print(n,m,l)
                exit (0)
        m+=1
    m=0
    n+=1


print("-1 -1 -1")
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
INF = 1e7

H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]

D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, sx, sy)]
heapify(PQ)
while PQ: # PQに候補がある限り
    _, ux, uy = heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heappush(PQ, (D[xx][yy], xx, yy))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])

### FIXED CODE ###

import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])