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

import sys
sys.setrecursionlimit(1000000)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

rest = K
ans = 0

def dfs(cost, aindex, bindex, score):
    global ans

    if K == cost:
        # print("1:", score, cost)
        # return score
        ans = max(score, ans)
        return

    elif K < cost:
        # print("2:", score, cost)
        # return score - 1
        ans = max(score - 1, ans)
        return 
    
    if aindex == N and bindex == M:
        # print("3:", score, cost)
        # return score
        ans = max(score, ans)

    elif aindex >= N:
        dfs(cost + B[bindex], aindex, bindex+1, score + 1)
    
    elif bindex >= M:
        dfs(cost + A[aindex], aindex+1, bindex, score + 1)

    else:
        dfs(cost + A[aindex], aindex+1, bindex, score + 1)
        dfs(cost + B[bindex], aindex, bindex + 1, score + 1)

dfs(A[0], 1, 0, 1)
dfs(B[0], 0, 1, 1)
print(ans)

### FIXED CODE ###

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

a, b = [0], [0]
for ai in A:
    a.append(a[-1] + ai)

for bi in B:
    b.append(b[-1] + bi)

# print(a, b)
ans = 0
bs = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in reversed(range(bs+1)):
        if a[i] + b[j] <= K:
            ans = max(ans, i + j)
            bs = j
            break

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

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

n,*a=map(int,open(0).read().split())
mod=10**9+7
lcm=1
for x in a:
    lcm=lcm*x//gcd(lcm,x)
ans=0
for x in a:
    ans+=(lcm//x)%mod
    ans%=mod
print(ans)

### FIXED CODE ###

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	lcm = 1
	for x in a:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= mod
	ans = sum(pow(x, mod - 2, mod) for x in a) % mod
	print(ans * lcm % mod)

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

N, Q = map(int, input().split())
S = input()
A = [0]*(N-1)
B = []
for n in range(N-1):
    if S[n:n+2] == "AC":
        A[n] += 1
for n in range(Q):
    l, r = map(int, input().split())
    B.append(sum(A[l-1:r-1]))
for n in range(Q):
    print(B[n])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
A = [0]*(N-1)
B = [0]
C = []
for n in range(N-1):
    if S[n:n+2] == "AC":
        A[n] += 1
for n in range(N-1):
    B.append(B[n]+A[n])
for n in range(Q):
    l, r = map(int, input().split())
    C.append(B[r-1]-B[l-1])
for n in range(Q):
    print(C[n])
### BUGGY CODE ###

import math

#要素の数を数えたい場合（key:数）
n=int(input())
li = list(map(int,input().split()))

dic={}
for i in li:
    if i not in dic:
        dic[i] = 1
    elif dic[i] >= 1:
        dic[i] += 1
        
#print(dic)

for i in range(n):
    cnt = 0
    dic[li[i]] -= 1
    for j in dic:
        cnt += dic[j]*(dic[j]-1)/2
    print(math.floor(cnt))
    dic[li[i]] += 1

### FIXED CODE ###

import math

#要素の数を数えたい場合（key:数）
n=int(input())
li = list(map(int,input().split()))

dic={}
for i in li:
    if i not in dic:
        dic[i] = 1
    elif dic[i] >= 1:
        dic[i] += 1
        
#print(dic)


cnt = 0
for j in dic:
    cnt += dic[j]*(dic[j]-1)/2
    #print(math.floor(cnt))

for i in range(n):
    print(math.floor(cnt - dic[li[i]]+1))
### BUGGY CODE ###

import math
n=int(input())
t=int(math.sqrt(n))
for i in range(1,n+1):
  ans=0
  for j in range(1,t):
    for k in range(1,t):
      for l in range(1,t):
        if j**2+k**2+l**2+j*k+k*l+j*l==i:
          ans+=1
  print(ans)

### FIXED CODE ###

import math
n=int(input())
t=int(math.sqrt(n))
ans=[0 for i in range(100001)]
for j in range(1,t):
  for k in range(1,t):
    for l in range(1,t):
      s=j**2+k**2+l**2+j*k+k*l+j*l
      if s<10001:
        ans[s]+=1
          
for m in range(1,n+1):
  print(ans[m])
### BUGGY CODE ###

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

lis = []

for i in set(a):
    if 2 <= a.count(i) <= 3:
        lis.append(i)
    elif 4 <= a.count(i):
        lis.append(i)
        lis.append(i)


lis.sort(reverse=True)
if len(lis) <= 1:
    ans = 0
else:
    ans = lis[0]*lis[1]

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from collections import Counter
a = Counter(a)
lis = []

for i,j in a.items():
    lis += [i]*(j//2)

#print(lis)

lis.sort(reverse=True)
if len(lis) <= 1:
    ans = 0
else:
    ans = lis[0]*lis[1]

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

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)%p
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(MAX+1):
		for i in xrange(MAX+1):
			dp[j+1][i] += dp[j][i]
			dp[j][i+1] += dp[j][i]
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup) / 2 + p) % p
solve()

### FIXED CODE ###

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p)+p) % p
solve()
### BUGGY CODE ###

n, x, t = map(int, input().split())

ans = 0
while True:
  if (n - x) <= 0:
    break
  if (n - x) > 0:
    ans += t
    
print(t)
  

### FIXED CODE ###

n, x, t = map(int, input().split())

ans = t

while True:
  if (n - x) <= 0:
    break
  
  if (n - x) > 0:
    ans += t
    n -= x

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

import math
import sys

prime_numbers = set()
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def query(l, r):
    count = 0
    for x in range(l, r + 1, 2):
        if is_primenumber(x) and is_primenumber((x + 1) // 2):
            count += 1
    print(count)


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1):
        is_primenumber(i)
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)


### FIXED CODE ###

import math
import itertools
import sys

prime_numbers = set()
table = [0 for i in range(10 ** 5 + 1)]
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def is_like_2017(x):
    return is_primenumber(x) and is_primenumber((x + 1) // 2)


def query(l, r):
    print(table[r] - table[l - 1])


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1, 2):
        if is_like_2017(i):
            table[i] += 1
    table = [x for x in itertools.accumulate(table)]
    Q = int(input())

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)
### BUGGY CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


### FIXED CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)
### BUGGY CODE ###

import queue
import numpy as np

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
dir4 = [[-1,0],[1,0],[0,-1],[0,1]]


def solveMaze(s, g):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]

    while not q.empty():
        now = q.get()
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            time = now[2] + 1
            g0 = g[0]
            g1 = g[1]

            if nextH == g[0] and nextW == g[1]:
                return time

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "#" or times[nextH][nextW] <= time:
                continue
            else:
                times[nextH][nextW] = time
                q.put([nextH, nextW, time])

    return -1


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            for gH in range(H):
                for gW in range(W):
                    if maze[gH][gW] == ".":
                        if sH != gH or sW != gW:
                            ans = max(ans, solveMaze([sH, sW], [gH, gW]))

print(ans)







### FIXED CODE ###

import queue
import numpy as np

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
dir4 = [[-1,0],[1,0],[0,-1],[0,1]]


def solveMaze(s):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]
    tmpAns = 0
    times[s[0]][s[1]] = 0
    while not q.empty():
        now = q.get()
        tmpAns = max(tmpAns, now[2])
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            nextTime = now[2] + 1

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "#" or times[nextH][nextW] <= nextTime:
                continue
            else:
                times[nextH][nextW] = nextTime
                q.put([nextH, nextW, nextTime])

    return tmpAns


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            ans = max(ans, solveMaze([sH, sW]))

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

N, Ma, Mb = map(int, input().split())

items = []
mas = []
mbs = []
costs = []
for i in range(N):
  ma, mb, c = map(int, input().split())
  mas.append(ma)
  mbs.append(mb)
  costs.append(c)

import itertools
l = list(itertools.product([False,True], repeat=N))

min_cost = 1000000000000000000
for comb in l[1:]:
  idx = [i for i, x in enumerate(comb) if x == True]
  cost = sum([costs[i] for i in idx])
  mass = [mas[i] for i in idx]
  mbss = [mbs[i] for i in idx]
  if ((sum(mass) // Ma) == (sum(mbss) // Mb)) & (sum(mass)%Ma==0) & (sum(mbss)%Mb==0) & (cost < min_cost):
    min_cost = cost
if min_cost == 1000000000000000000:
  print("-1")
else:
  print(min_cost)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())

items = []
mas = []
mbs = []
costs = []
for i in range(N):
  ma, mb, c = map(int, input().split())
  mas.append(ma)
  mbs.append(mb)
  costs.append(c)

max_cost = 5000
dp = [[[max_cost for k in range((N+1)*10)] for j in range((N+1)*10)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
  for j in range(N*10):
    for k in range(N*10):
      if dp[i][j][k] == max_cost:
        continue
      if dp[i+1][j][k] > dp[i][j][k]:
        dp[i+1][j][k] = dp[i][j][k]
      if dp[i+1][j+mas[i]][k+mbs[i]] > dp[i][j][k] + costs[i]:
        dp[i+1][j+mas[i]][k+mbs[i]] = dp[i][j][k] + costs[i]
        
min_cost = max_cost
for wa in range(1, N*10):
  for wb in range(1, N*10):
    if (wa * Mb != wb * Ma):
      continue;
    if min_cost > dp[N][wa][wb]:
      min_cost = dp[N][wa][wb]

  
if min_cost == max_cost:
  print("-1")
else:
  print(min_cost)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def addc(p,e,c,total,check):
  c[p] += total
  total = c[p]
  check.append(p)
  if(len(e[p]) == 0):
    return 0

  else:
    for i in e[p]:
      if(i not in check):
        addc(i,e,c,total,check)

  return 0

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

e = [ [] for i in range(n + 1)]
c = [0 for i in range(n + 1)]

for i in range(n-1):
  a,b = map(int,input().split())
  e[a].append(b)
  e[b].append(a)

for i in range(q):
  p,x = map(int,input().split())
  c[p] += x

_ = addc(1,e,c,0,[])

c.pop(0)

print(*c)

### FIXED CODE ###

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

def addc(p,b):
  for i in e[p]:
    if(i == b):
      continue
    c[i] += c[p]
    addc(i,p)

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

e = [ [] for i in range(n + 1)]
c = [0]*(n+1)

for i in range(n-1):
  a,b = map(int,input().split())
  e[a].append(b)
  e[b].append(a)

for i in range(q):
  p,x = map(int,input().split())
  c[p] += x

addc(1,-1)

print(*c[1:])
### BUGGY CODE ###

from collections import Counter
import heapq

n=int(input())
word=[]
for i in range(n):
    word.append(input())

word_count=Counter(word)

ans=[k for k, v in word_count.items() if v == max(word_count.values())]
cnt=len(ans)
heapq.heapify(ans)
for i in range(cnt):
    print(heapq.heappop(ans))

### FIXED CODE ###

from collections import Counter
import heapq

n=int(input())
word=[]
for i in range(n):
    word.append(input())

word_count=Counter(word)
ma=max(word_count.values())

ans=[k for k, v in word_count.items() if v == ma]
cnt=len(ans)
heapq.heapify(ans)
for i in range(cnt):
    print(heapq.heappop(ans))
### BUGGY CODE ###

n=int(input())
c=0
for i in range(1,n+1):
    j=1
    while j*i<n:
        c+=1
        j+=1
print(c)        

### FIXED CODE ###

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

a,b,n = map(int,input().split())
ma = 0
"""
if(n<=b):
    ma = (a*n)//b - (a* (n//b))
else:
    ma = (a*(b-1))//b - (a*((b-1)//b))
    num = max([(a*x)//b - (a*(x//b)) for x in range(b,n+1)])
    print(num)
    if(ma < num):
        ma = num
"""
ma = max([(a*x)//b - (a*(x//b)) for x in range(0,n+1)])
print(ma)

### FIXED CODE ###

a,b,n = map(int,input().split())
ma = 0

if(n<b):
    ma = (a*n)//b - (a* (n//b))
else:
    ma = (a*(b-1))//b - (a*((b-1)//b))
    """
    for x in range(b,n+1):
        
        num = (a*x)//b - (a*(x//b))
        if(ma > num):
            break
        ma = num
    """

print(ma)
### BUGGY CODE ###

N = int(input())

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

for i in range(N-1):
    for j in range(i+1,N):
        if H[j] - (H[i]-1) < 0:
            print('No')
            exit()
print('Yes')

### FIXED CODE ###

N = int(input())

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

for i in range(N-1,0,-1):
    if 2 <= H[i-1] - H[i]:
        print('No')
        exit()
    else:
        if (H[i-1] - 1) == H[i]:
            H[i-1] -= 1
print('Yes')
### BUGGY CODE ###

import sys
from math import sqrt, ceil

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

if n == 1:
    print(p)
    sys.exit()

if p == 1:
    print(1)
    sys.exit()

ans = []
for i in range(1, p):
    value = i ** n
    if value > p:
        break

    if p % value == 0:
        ans.append(i)

# print(ans)
print(max(ans))


### FIXED CODE ###

from math import sqrt, floor, log


def is_prime(num):
    if num <= 1:
        return False

    for i in range(2, floor(num / 2) + 1):
        if i == num:
            break
        if num % i == 0:
            return False
    return True


def get_divisors3(num):
    ans = []
    value = num
    i = 2
    while (i * i) <= num:
        count = 0
        while value % i == 0:
            count += 1
            value = value // i

        if count != 0:
            ans.append((i, count))
        i += 1
    return ans


def main():
    n, p = [int(i) for i in input().split()]
    if n == 1:
        print(p)
    elif p == 1:
        print(1)
    else:
        ds = get_divisors3(p)
        ans = 1
        for d in ds:
            if d[1] >= n:
                ans *= d[0] ** (d[1] // n)
        print(int(ans))


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

from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  if z[x][0]==-1:
    z[x][0]=z[x][1]=1
    for y in v[x]:
      if y!=p:
        f(y,x)
      	z[x][0]=(z[x][0]*z[y][1])%mod
        z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  if z[x][0]==-1:
    z[x][0]=z[x][1]=1
    for y in v[x]:
      if y!=p:
        f(y,x)
      	z[x][0]=(z[x][0]*z[y][1])%mod
        z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod
### BUGGY CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(lambda x: int(x)-1, input().split()))
ti, tj = list(map(lambda x: int(x)-1, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 探索時に移動する方向
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h, w), INF)
dist = [[INF for j in range(w)] for i in range(h)]

from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    (i, j) = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(di)):
        ni, nj = i+di[v], j+dj[v]
        if (ni<0 or ni>=h or nj<0 or nj>=w):
            continue # マップの境界
        if (s[ni][nj] == '#'):
            continue # 壁
        if (dist[ni][nj]<=d):
            continue # 探索済みコスト以上
        dist[ni][nj] = d
        q.append((ni, nj))
    # 移動Bによるコスト
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni, nj = i+ei, j+ej
            if (ni<0 or ni>=h or nj<0 or nj>=w):
                continue # マップの境界
            if (s[ni][nj] == '#'):
                continue # 壁
            if (dist[ni][nj]<=d):
                continue # 探索済みコスト以上
            dist[ni][nj] = d+1
            q.append((ni, nj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, Ch, Cw)]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, h, w = heappop(q)
        if h==Dh and w==Dw:
            break

        for hh, ww in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            if costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                heappush(q, (cost, hh, ww))

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh==0 and dw==0:
                    continue
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                if costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, hh, ww))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()