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

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])
    # print(time)
    # print(f)
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1

ans = -1
for i in range(1,max_end):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

# print(f)
print(ans)


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

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

import sys

input = sys.stdin.readline


def main():
    N = int(input())
    TA = [[int(x) for x in input().split()] for _ in range(N)]

    now = TA[0]
    for t, a in TA[1:]:
        i = 1
        while now[0] > t * i or now[1] > a * i:
            i += 1
        now[0] = t * i
        now[1] = a * i

    print(now[0] + now[1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    N = int(input())
    TA = [[int(x) for x in input().split()] for _ in range(N)]

    now = TA[0]
    for t, a in TA[1:]:
        i = max(now[0] //t , now[1] // a)
        while now[0] > t * i or now[1] > a * i:
            i += 1
        now[0] = t * i
        now[1] = a * i

    print(now[0] + now[1])


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

n = int(input())
x = input()

ppc = {}
ppc[0] = 0
def popcount(n):    
  if n in ppc:
    return ppc[n]  
  if n == 0:
    return 0
  b = bin(n).count('1')  
  tmp = n%b
  ppc[n] = popcount(tmp) + 1
  return ppc[n]

for i in range(2*10**5+1):
  popcount(i)
  
bit = int('0b'+x,0)
bn = x.count('1')
for i in range(n):
  if x[i] == '1':   
    bt = bn-1
    if bt == 0:
      print(0)
      continue
  else:
    bt = bn+1  
  tmp = bit ^ (1<<(n-i-1))
  print(ppc[tmp%bt]+1)
  

### FIXED CODE ###

n = int(input())
X = input()

def goes_to_zero(n):
  cnt = 0
  while(n > 0):
    n %= bin(n).count('1')
    cnt += 1
  return cnt
  
c1 = X.count('1')
xint = int(X,2)
xtp = xint % (c1 + 1)
if (c1 - 1) == 0:  
  xtm = 0
else:
  xtm = xint % (c1 - 1)
  
for i in range(n)  :
  if X[i] == '0':
    print(goes_to_zero( (xtp + pow(2,n-1-i,(c1+1))) % (c1+1) ) + 1)
  else:
    if (c1-1) == 0:
      print(0)
    else:
      print(goes_to_zero( (xtm - pow(2,n-1-i,(c1-1)) ) % (c1-1) ) +1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
mod=10**18
for i in A:
    ans=ans*i
if ans>mod:
    ans=-1
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
mod=10**18
for i in A:
    if i==0:
        ans=0
        break
    elif i==1:
        continue
    elif ans!=-1:
        ans=ans*i
        if ans>mod:
            ans=-1
print(ans)
### BUGGY CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

for i, A in enumerate(map(int, input().split())):
    if i == 0: Asym = [A % M]
    else: Asym.append((Asym[-1] + A) % M)
# print(Asym)
    
ans = Asym.count(0)
for sym in set(Asym):
    # print(sym, Asym.count(sym), ans)
    cnt = Asym.count(sym)
    ans +=  int(cnt * (cnt -  1) / 2)

print(ans)



### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

#from fractions import gcd
#from math import gcd
import numpy as np
#import sys
#input = sys.stdin.readline
mod = 10**9+7

def obtain_ps(n):
    ps={}
    while(n>1):
        for i in range(2, int(n**0.5)+1):
            if not n%i==0:
                continue
            i_primary=True
            for j in range(2, int(i**0.5)+1):
                if j %i:
                    i_primary=False
                    break
            if not i_primary:
                continue
            count=1
            r=i
            while(not n%r):
                count +=1
                r*=i
                if count > 10:
                    return -1
            count-=1
            ps[i]=count
            n=n/(i**count)
        if int(n**0.5)+1<=2:
            ps[n]=1
            n=1
    return ps

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

ps={}
for s in A:
    ps_tmp=obtain_ps(s)
    for k,v in ps_tmp.items():
        if k in ps.keys():
            ps[k]=max(v, ps[k])
        else:
            ps[k]=v

lcm=np.product([k**v for k,v in ps.items()])

ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
### BUGGY CODE ###

import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
a.sort()
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
#print(lcm_list(a))
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans=ans%(mod)+(n//a[i])%mod
print(ans%mod)

### FIXED CODE ###

import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans+=(n//a[i])
print(ans%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
for i in a:
    result*=i
if result>10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
if 0 in a:
    print(0)
else:
    for i in a:
        result*=i
        if result>10**18:
            print(-1)
            break
    if result<=10**18:
        print(result)
### BUGGY CODE ###

s = input()
k = int(input())

count = 0
for i in s:
  if i == "1":
    count += 1
  else :
    count += int(i)**k
  if count >= k:
    print(i)
    break
  

### FIXED CODE ###

s = input()
k = int(input())

answer = 1
if len(s) == 1:
  answer = s
else :
  for i in range(k):
    if s[i] != "1":
      answer = s[i]
      break
print(answer)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
d = []
for x1, x2 in zip(x, x[1:]):
    d.append(x2 - x1)
mod = 10 ** 9 + 7
base = 1
for i in range(1, n):
    base *= i
ans = 0
b = base
for i, di in enumerate(d):
    ans += (base * di)  % mod
    ans %= mod
    base += b // (i + 2)
    base % mod
print(ans)


### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
d = []
for x1, x2 in zip(x, x[1:]):
    d.append(x2 - x1)
mod = 10 ** 9 + 7
base = 1

P = 10**9 + 7
N = n+2
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

for i in range(1, n):
    base *= i
    base %= mod
ans = 0
b = base
for i, di in enumerate(d):
    ans += (base * di)  % mod
    ans %= mod
    base += b * inv_t[i+2]
    base % mod
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
        A.append(int(input()))
m = max(A)
for i in range(N):
        if A[i] == m:
                A.remove(m)
                print(max(A))
                A.insert(i,m)
        else:
                print(m)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
        A.append(int(input()))
m = max(A)
n = A.index(m)
A.remove(m)
m1 = max(A)
for i in range(n):
        print(m)
print(m1)
for i in range(N-1-n):
        print(m)
### BUGGY CODE ###

n, Y = [int(s) for s in input().split(' ')]
 
for x in range(n, -1, -1):
    if Y < x*10000 or n < x:
        continue
    
    for y in range(n-x, -1, -1):
        if Y < x*10000+y*5000 or n < x+y:
            continue
            
        z = int((Y-x*10000-y*5000)/1000)
        if Y == x*10000+y*5000+z*1000 and n == x+y+z:
            print('{} {} {}'.format(x, y, z))
            exit()
            
print('-1 -1 -1')

### FIXED CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        if (y - ten_th * 10000 - five_th * 5000) % 1000 == 0:
            th = int((y - ten_th * 10000 - five_th * 5000) / 1000)
            if n == ten_th + five_th + th:
                print('{} {} {}'.format(ten_th, five_th, th))
                exit()
print('-1 -1 -1')
### BUGGY CODE ###

import heapq
from heapq import heapify
n,m = map(int,input().split())
A = list(map(int,input().split()))
B = [0]*m
C = [0]*m
for i in range(m):
    B[i],C[i] = map(int,input().split())

heapq.heapify(A)
for i in range(m):
    b,c = B[i],C[i]
    for i in range(b):
        if A[0]<c:
            heapq.heapreplace(A,c)
        else:
            break
print(sum(A))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 0:
    return 1
  ans = mpow(a,n//2)**2%mod
  if n%2==1:
    ans *= a
  return ans
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*mpow(i,mod-2)%mod
  return ans

print((mpow(2,n)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(4,3))

### FIXED CODE ###

import math
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*pow(i,mod-2,mod)%mod
  return ans

print((pow(2,n,mod)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(n,a))
### BUGGY CODE ###

#S = list(input())

N,K,Q=map(int,input().split())
#S=list(map(int,input().split()))


A=[]
for _ in range(Q):
    A.append(int(input()))

for n in range(N):
    AC = A.count(n+1)
    score = K - Q + AC
#    print(score)
    if score > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

from itertools import groupby

N,K,Q=map(int,input().split())
#S=list(map(int,input().split()))


A=[0]*Q
for i in range(Q):
    A[i] = int(input())

ans=[K-Q]*N

A.sort()

for key,value in groupby(A):
    ans[key-1] = K-Q+ len(list(value))

for n in ans:
    if n > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 1001001001
dp = [inf] * (n+1)

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

for i in range(n):
    for j in range(i + k):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 1001001001
dp = [inf] * (n+1)

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

for i in range(n):
    for j in range(k):
        if i + j >= n:
            break
        dp[i + j] = min(dp[i + j], dp[i-1] + abs(h[i+j] - h[i-1]))
print(dp[n-1])
### BUGGY CODE ###

def main():
    n = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x >= y:
            return x
        else:
            return y

    def init(init_val):
        # set_val
        for i in range(n+1):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while p < q:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 0

    # num: n以上の最小の2のべき乗
    num = 2**n.bit_length()
    seg = [ide_ele]*2*num

    X = [0]*(n+1)
    for i in range(n):
        update(H[i], query(0, H[i]+1)+A[i])
    print(query(0, n+2))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x >= y:
            return x
        else:
            return y

    def init(init_val):
        # set_val
        for i in range(n+1):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while p < q:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 0

    # num: n以上の最小の2のべき乗
    num = 2**n.bit_length()
    seg = [ide_ele]*2*num

    X = [0]*(n+1)
    for i in range(n):
        update(H[i], query(0, H[i]+1)+A[i])
    print(query(0, n+2))

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

N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [[0]*N for _ in range(60)]

for i in range(N):
    dp[0][i] = A[i] - 1

for k in range(1, 60):
    for n in range(N):
        dp[k][n] = dp[k - 1][dp[k - 1][n]]

res = []
for i in range(60):
    if (K>>i)&1:
        res.append(i)
    
pos = 0
for i in res:
    pos = dp[i][pos]
print(pos + 1)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
dist = [-1]*(N+1)

d = {i:[] for i in range(1, N+1)}
for i, j in enumerate(A, start=1):
    d[i].append(j)

dist[1] = 0
q = [1]
cycle = 0
ls = 0
while q:
    a = q.pop()
    for b in d[a]:
        if dist[b]==-1:
            dist[b] = dist[a] + 1
            q.append(b)
        elif dist[b]==0 or dist[b]:
            cycle = dist[a] + 1 - dist[b]
            ls = b
            break

b = (K-dist[ls])%cycle if K>dist[ls] else K
c = dist[ls]+b if K>dist[ls] else K
for i, j in enumerate(dist):
    if j==c:
        print(i)
        break
### BUGGY CODE ###

N, K = map(int, input().split())
seq = []
for i in range(N):
    a, b = map(int, input().split())
    for j in range(b):
        seq.append(a)

seq.sort()
print(seq[K-1])


### FIXED CODE ###

from collections import defaultdict
N, K = map(int, input().split())
seq = defaultdict(lambda: 0) 
for i in range(N):
    a, b = map(int, input().split())
    seq[a] += b

values = list(seq.keys())

values.sort()
ans = 0
for i in range(len(values)):
    K -= seq[values[i]]
    if(K<=0):
        print(values[i])
        break
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
r = 0
for i in range(n):
    p, x = 0, 0
    for j in range(n-i):
        p += A[i+j]
        x ^= A[i+j]
        if p == x:
            r += 1
print(r)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
j = 0
for i in range(n):
    while j < n and not (s & A[j]):
        s ^= A[j]
        j += 1
    ans += j-i
    s ^= A[i]
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Here your code !
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(out)
    elif out==N:
        out2.append(in1)
len_in2=len(in2)
for q in range(len_in2):
    if in2[q] in out2:
        print("POSSIBLE")
        break
    elif q+1==len_in2:
        print("IMPOSSIBLE")
    else:
        continue

### FIXED CODE ###

a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)
#print(matched_list)
if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

N = int(input())
s = ["".join(sorted(list(input()))) for i in range(N)]

#出現文字列
sdict = {}

ans = 0

for i in range(N):

    s_i = str(s[i])

    if s_i in sdict:
        #組み合わせが増えるので
        sdict[s_i]+= 1
        continue

    for j in range(i+1,N):
        sdict[s_i] = 1

for i in sdict.values():
    ans += i*(i-1)//2

print(ans)


### FIXED CODE ###

N = int(input())
s = ["".join(sorted(input())) for i in range(N)]

#print(s)

#出現文字列
sdict = {}

for i in range(N):

    s_i = str(s[i])

    if s_i in sdict:
        #組み合わせが増えるので
        sdict[s_i]+= 1
        continue

    else:
        sdict[s_i] = 1

ans = 0
for i in sdict.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

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

max_count = 0

for i in range(n-k+1):
    count = sum(p_list[i:i+k])
    max_count = max(max_count,count)

print(max_count/2 + k/2)

### FIXED CODE ###

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

max_count = 0
summary = 0
 
for i in range(n-k+1):
    if i == 0:
        summary = sum(p_list[i:i+k])
    else:
        summary += p_list[i+k-1]-p_list[i-1]
    max_count = max(max_count,summary)
 
print(max_count/2 + k/2)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())

a = [[False]*(w+2)]
for y in range(h):
    a += [[False] + [x!='#' for x in input()] + [False]]
a += [[False]*(w+2)]

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

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 = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = deque()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.append((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.append((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    while now:
      h,w = now.popleft()
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

### FIXED CODE ###

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 = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])